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

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

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

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

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

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

Алгоритм быстрой сортировки 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

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

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

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

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

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, нажмите здесь .