퀵 정렬 알고리즘

오름차순 정렬을 가정했을 때, 피봇이라는 기준값으로 왼쪽에는 기준값보다 작은 부분집합을 형성시키고 오른쪽에는 기준값보다 큰 부분집합을 형성시킨다. 분할정복을 이용하기 때문에 lgN의 깊이만큼 재귀호출을 하고, 깊이마다 배열의 길이인 N만큼 비교하기 때문에 총 평균 시간복잡도는 NlgN만에 정렬시킬 수 있다

 

피봇을 잡는 기준은 다양하며 특정 피봇 위치를 잡았을 때 엄청 좋다라는 것은 없다. 다만 합병 정렬과 달리, 피봇에 따라 비균등하게 부분집합들이 나눠질 수 있기 때문에 unstable-sort로 분류를 한다. 만일 정렬된 배열에 대해서 퀵 소트를 한다고 하면, 퀵 정렬 알고리즘에 따라서 lgN의 깊이가 아닌 N의 깊이만큼 내려가게 된다. 따라서 최악의 시간복잡도 O(N^2)이 나오게 된다

 

1) 리스트 맨 끝 값으로 피봇을 잡았을 때

- 두 인덱스 변수를 이용해서, 피봇값보다 작다면 두 인덱스에 해당하는 값들은 switching한다

 

2) 리스트 맨 앞 값으로 피봇을 잡았을 때

- 1번과 유사하지만 끝에서부터 탐색한다는 차이점이 있다

 

 

17번의 부등호 방향만 바꿔준다면 오름차순을 내림차순으로 바꿀 수 있다