[Algorithm] 퀵 정렬 알고리즘 (Quick Sort Algorithm)

By | 2018-05-22

프로그래밍 문제를 풀면서 리스트 정렬을 해야 하는 경우가 많아서 쉬운 알고리즘 부터 공부를 하기 시작했다. Quick Sort가 이해하기 쉬운 알고리즘 중 하나 인듯하여서 SW Expert Academy에서 제공하는 코드를 보면서 공부를 해보았다 (출처 1). 아래 코드는 SW Expert Academy에서 제공하는 코드를 가져와 정말 살짝 변경하였다.

위 코드를 실행하여 [3, 2, 1, 3, 7, 6, 5, 4, 2]를 정렬하는 순서를 아래 그림으로 정리해보았다.

그림 1. Quick Sort 예제 순서도

순서도

  • Start: 먼저 Pivot이라고 해서 기준값을 정하고, i 와 j 포인터를 리스트 처음과 끝에 위치시킨다.
  • Step1 (S1): i 포인터가 가리키는 값이 Pivot보다 클 때 까지 i를 오른쪽으로 이동한다. (i++를 해줌)
  • S2: j 포인터가 가리키는 값이 Pivot보다 크면 j를 왼쪽으로 이동한다 (j–를 해줌). 위 예제의 경우 마지막 j 포인트가 가리키는 값이 pivot보다 작기 때문에 움직이지 않았다.
  • S3: i와 j가 가리키는 값을 서로 변경한다.
  • S4: i와 j의 위치가 서로 동일하거나 i가 j보다 왼쪽에 위치 할 때 까지 S2와 S3을 반복한다.
  • S5: Pivot이 가리키는 값과 j가 가리키는 값을 서로 변경한다.
  • S6: j-1 이전 리스트와 j+1 이후 리스트를 나누어서 S1~S5를 계속 반복한다.
  • END: 순서가 정리된 것을 확인할 수 있다.

생각보다 단순한 알고리즘인데 이것을 이해하는데 거의 하루가 걸렸다. 그리고 여러 번 혼자서 다시 작성을 해보았지만, 아직도 한 번에 제대로 코딩을 하지 못하고 있다. 아래 출처 2에 따르면 Quick Sort의 경우 평균 실행 시간이 O(log N)이고 최악의 경우 O(N^2)만큼 걸린다고 한다.  개인적으로 공부를 하고 싶어서 해당 그림을 만들어보았다. 하지만, 출처 2 사이트를 방문하면 동영상으로 설명이 더 잘되어있다.

출처

  1. https://www.swexpertacademy.com
  2. http://zeddios.tistory.com/35

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *