[알고리즘/퀵정렬] #Quick_Sort / in Python

퀵 정렬

- 숫자를 오름차순으로 정렬하는 프로그램 
- 기존 선택, 버블, 삽입은 N^2이라는 시간 복잡도를 가지고 있다.
- 데이터가 무수히 많아 짐에 따라 좀 더 빠른 정렬을 생각 해볼 필요가 있다.
- 이때 생각해낸 것이 퀵정렬이다.
- 특정한 배열이 있을 때 "분할 정복" 알고리즘을 쓴다 & 재귀 알고리즘을 이용한 정렬이다.

---

기본원리

가운데 pivot값을 정한 후

작은값 + pivot값 + 큰값

같은 형식으로 정리하는 원리 이다.

코드는 직관성 있고 이해하기 쉽지만 효율적이지 않다.
-메모리 사용 측면에서 좋지 못한 코드이다.

1. 리스트의 정 가운데 있는 값을 pivot 값을 선택합니다.

2. 시작 인덱스(low)는 계속 증가 시키고, 끝 인덱스(high)는 계속 감소 시키기위한 while 루프를 두 인덱스가 서로 교차해서 지나칠 때까지 반복시킵니다.

3. 시작 인덱스(low)가 가리키는 값과 pivot 값을 비교해서 더 작은 경우 반복해서 시작 인덱스 값을 증가시킵니다. (pivot 값보다 큰데 좌측에 있는 값을 찾기 위해)

4. 끝 인덱스(high)가 가리키는 값과 pivot 값을 비교해서 더 작은 경우 반복해서 끝 인덱스 값을 감소시킵니다. (pivot 값보다 작은데 우측에 있는 값을 찾기 위해)
5. 두 인덱스가 아직 서로 교차해서 지나치치 않았다면 시작 인덱스(low)가 가리키는 값과 끝 인덱스(high)가 가리키는 값을 상호 교대(swap) 시킵니다. (잘못된 위치에 있는 두 값의 위치를 바꾸기 위해)
6. 상호 교대 후, 다음 값을 가리키기 위해 두 인덱스를 각자 진행 방향으로 한 칸씩 이동 시킵니다.
7. 두 인덱스가 서로 교차해서 지나치게 되어 while 루프를 빠져나왔다면 다음 재귀 호출의 분할 기준점이될 시작 인덱스를 리턴합니다.

 

코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

def quick_sort(arr):     if len(arr) <= 1:         return arr       pivot = arr[len(arr)//2]     left_arr, equal_arr, right_arr = [], [], []       for num in arr:         if num < pivot: #num을 한칸씩 오른쪽으로 이동 // 피벗보다 작은값을 만날때 까지              left_arr.append(num)         elif num > pivot: #num을 왼쪽으로 한칸씩 이동 // 피벗보다 큰 값 만날 때 까지             right_arr.append(num)         else: #엇갈림             equal_arr.append(num)       return quick_sort(left_arr) + equal_arr + quick_sort(right_arr)

 

---

 

 

최적화

최적화를 위해서는 2개의 함수를 사용하는 것으로 한다.
1. partition() 함수
2. sort() 함수
partion() 함수는 단순히 쪼개고 왼쪽, 오른쪽으로 정렬하는 형식으로 하고, sort() 함수는 재귀하는목적으로 사용한다.

블로그 참고

www.daleseo.com/sort-quick/

 

[알고리즘] 퀵 정렬 - Quick Sort (Python, Java)

---

#빅오(Big O) 표기법
퀵 정렬의 시간 복잡도는 O(N*logN)가 된다. (수를 대충 대입해 보면 거의 상수이다.)
평균적으로 O(N*logN) 가 나온다.

#선택정렬
#1 2 3 4 5 6 7 8 9 10
# N^2 = 10 * 10 = 100 (대략적)

#퀵정렬
#1 2 3 4 5 >>> 5 * 5 = 25
#6 7 8 9 10  >>> 5 * 5 = 25
#반반 을 쪼개서 한다.

#약점
피벗값의 설정이 최악인 경우 O(N^2)이 나오는 경우도 있다.
#예를 들어 이미 정렬된 경우
#[1,2,3,4,5,6,7,8,9,10] 시간 복잡도는 N^2 가 나온다.
#위에 문제를 삽입 정렬을 이용하면 매우 빠르게 이용할 수 있다.

결론
#데이터의 맞게 정렬 알고리즘을 사용하는게 맞다.

#퀵정렬 소스코드에서 두가지 부분에서 오름차순에서 내림차순으로 바꾸는 것은?