Структура данных и алгоритмы — Быстрая сортировка

Быстрая сортировка является высокоэффективным алгоритмом сортировки и основана на разбиении массива данных на меньшие массивы. Большой массив разделен на два массива, один из которых содержит значения, меньшие, чем заданное значение, скажем, pivot, на основе которого создано разделение, а другой массив содержит значения, превышающие значение pivot.

Быстрая сортировка разделяет массив, а затем дважды вызывает себя рекурсивно для сортировки двух результирующих подмассивов. Этот алгоритм достаточно эффективен для наборов данных большого размера, поскольку его средняя и наихудшая сложность составляют Ο (n ² ), где n — количество элементов.

Раздел в быстрой сортировке

Следующее анимированное представление объясняет, как найти значение pivot в массиве.

Сводное значение делит список на две части. И рекурсивно мы находим стержень для каждого подсписка, пока все списки не содержат только один элемент.

Алгоритм быстрой сортировки Pivot

Основываясь на нашем понимании разбиения в быстрой сортировке, мы теперь попытаемся написать алгоритм для него, который заключается в следующем.

Step 1 − Choose the highest index value has pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is new pivot

Quick Sort Pivot Pseudocode

Псевдокод для вышеуказанного алгоритма может быть получен как —

function partitionFunc(left, right, pivot)
   leftPointer = left
   rightPointer = right - 1

   while True do
      while A[++leftPointer] < pivot do
         //do-nothing            
      end while
		
      while rightPointer > 0 && A[--rightPointer] > pivot do
         //do-nothing         
      end while
		
      if leftPointer >= rightPointer
         break
      else                
         swap leftPointer,rightPointer
      end if
		
   end while 
	
   swap leftPointer,right
   return leftPointer
	
end function

Алгоритм быстрой сортировки

Используя рекурсивный алгоритм pivot, мы получаем меньшие возможные разделы. Каждый раздел затем обрабатывается для быстрой сортировки. Определим рекурсивный алгоритм быстрой сортировки следующим образом:

Step 1 − Make the right-most index value pivot
Step 2 − partition the array using pivot value
Step 3 − quicksort left partition recursively
Step 4 − quicksort right partition recursively

Быстрая сортировка псевдокода

Чтобы получить больше, давайте посмотрим псевдокод для алгоритма быстрой сортировки —

procedure quickSort(left, right)

   if right-left <= 0
      return
   else     
      pivot = A[right]
      partition = partitionFunc(left, right, pivot)
      quickSort(left,partition-1)
      quickSort(partition+1,right)    
   end if		
   
end procedure

Чтобы узнать о быстрой реализации сортировки на языке программирования C, пожалуйста, нажмите здесь .