데이터 구조 및 알고리즘-빠른 정렬

빠른 정렬은 매우 효율적인 정렬 알고리즘이며 데이터 배열을 더 작은 배열로 분할하는 것을 기반으로합니다. 큰 배열은 두 개의 배열로 분할되며, 그 중 하나는 지정된 값 (예 : 피벗)보다 작은 값을 보유하며 파티션이 만들어지는 기준이고 다른 배열은 피벗 값보다 큰 값을 보유합니다.

Quicksort는 배열을 분할 한 다음 자신을 재귀 적으로 두 번 호출하여 두 개의 결과 하위 배열을 정렬합니다. 이 알고리즘은 평균 및 최악의 복잡성이 각각 O (n 2 ) 이기 때문에 대규모 데이터 세트에 대해 매우 효율적입니다 .

빠른 정렬의 파티션

다음 애니메이션 표현은 배열에서 피벗 값을 찾는 방법을 설명합니다.

피벗 값은 목록을 두 부분으로 나눕니다. 그리고 재귀 적으로 모든 목록에 하나의 요소 만 포함될 때까지 각 하위 목록의 피벗을 찾습니다.

빠른 정렬 피벗 알고리즘

빠른 정렬의 분할에 대한 이해를 바탕으로 이제 다음과 같은 알고리즘을 작성해 보겠습니다.

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

빠른 정렬 피벗 의사 코드

위의 알고리즘에 대한 의사 코드는 다음과 같이 파생 될 수 있습니다.

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

빠른 정렬 알고리즘

피벗 알고리즘을 재귀 적으로 사용하면 가능한 더 작은 파티션으로 끝납니다. 그런 다음 각 파티션이 빠른 정렬을 위해 처리됩니다. 다음과 같이 quicksort에 대한 재귀 알고리즘을 정의합니다.

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 프로그래밍 언어의 빠른 정렬 구현에 대해 알아 보려면 여기 를 클릭하십시오 .