[알고리즘] 분할정복과 퀵정렬

Hyo Kyun Lee·2022년 1월 11일
0

알고리즘

목록 보기
5/45

4. 퀵정렬

분할정복을 활용하여 data를 정렬하는 알고리즘을 일컫는다.

특정 값(pivot)을 기준으로 왼쪽에 pivot보다 작은 숫자(혹은 특정 기준을 만족하는 값들), 오른쪽에 pivot보다 큰 숫자(혹은 특정 기준을 만족하는 값들)를 위치해가며 data를 정렬해가는 방법을 의미한다.

4-1. 분할정복

큰 문제를 여러 작은 문제들로 나눈 후, 작은 문제를 풀어가면서 최종적으로 큰 문제의 해답을 찾는 방법론을 말한다.

4-2. 퀵정렬에서의 분할정복

퀵정렬을 하는 과정은 강의 사이트에서 참고할 수 있다.

여기서의 핵심은 pivot이 정렬완료되는 시점(탐색이 엇갈리는 시점, 즉 pivot보다 작은 값의 인덱스가 큰 값의 인덱스보다 작을 때)에서 pivot 기준으로 왼쪽/오른쪽 data들이 분할되어 정렬되었다는 점이다.

4-3. 엇갈리는 시점, 퀵정렬에서의 분할정복 의미

엇갈리는 시점에서 pivot은 위치가 바뀔 수도 있고, 안 바뀔 수도 있다.

바뀌든 안바뀌든 이때 중요한 점은 pivot 정렬이 완료되었을때

  • 그 이후 정렬이 진행되는 값들은 정렬 완료된 값을 건드리지 않는다(즉 정렬이 종료된 시점 이후엔 정렬 대상에 포함되지 않는다).
  • pivot 값이 정렬되는 시점에서 왼쪽, 오른쪽으로 혹은 특정 기준으로 data가 분할된다.
  • 또한 pivot 값을 정렬해나가는 과정 자체가 왼쪽, 오른쪽 나누면서 data를 정렬해나간다.
  • 다만 분할된 data들을 따로 보지 않고, 전체적으로 정렬해나간다(다만 pivot 기준으로 분할이 되고 분할된 data들을 세부적으로 정렬해나간다는 점에서 분할정복으로 볼 수 있다).

4-4. 시간 복잡도

직관적인 예시를 들어보면 이해가 쉬워진다.

  • 기존 O(N^2)의 시간복잡도를 가진 선택, 삽입정렬 등은 data가 N개가 있을때 N개 만큼 순회를 하면서 정렬을 하므로 N*N의 시간복잡도를 가졌다.
  • 퀵정렬의 경우 분할정복을 활용하는데, 예를 들어 10개 data에서 분할된 (N/2=5, N/2=5)마다 알고리즘을 적용한다하면 O(55) + O(55)의 시간복잡도를 가지게 된다.
  • 결론적으로 O(102(=100)) > O(25) + O(25)이게 되어 분할정복의 시간복잡도가 더 유리하게 된다(분할정복의 시간복잡도는 O(Nlog(N))).

4-5. 파이썬 pseudo 코드

파이썬은 list index error가 발생하기 때문에, 반복문에서 index(i, j 등)값의 범위를 정확히 지정해주어야 오류가 발생하지 않는다.

array = [3, 10, 5, 1, 7, 6, 4, 2, 8, 9]
arrayLength = len(array)


##분할정복을 하면서 부분집합을 나누게 되는데
##부분집합의 처음 숫자, 마지막 숫자
##부분집합의 원소가 1개일 경우
##처음 숫자가 마지막 숫자보다 크거나 같은 경우로 빼면
##그대로 return
##기본적으로 분할정복은 한 함수를 선언하고, 이에 따라 각 부분집합에 대해 분할정복을 수행하는 방식으로 진행한다.
##즉 재귀법으로 진행
# def quickSort(array, dividedStart, dividedFinal)
# if (dvidedStart >= dividedFinal):
# return

## pivot값을 설정
## 큰 값 찾을때(처음에서 끝 순으로) : dividedStart + 1
## 작은 값 찾을때(끝에서 처음 순으로) : dividedFinal
##key = pivot
# key = dividedStart
# i = divdiedStart + 1
# j = dividedFinal

##순회 시 연산종료시점은 엇갈리는 시점(그 전까지 반복)
##엇갈리는 시점에서 pivot값과 큰 값(j index)을 교체
##그 전까지는 탐색하면서 pivot값보다 작은 값, 큰 값을 찾아 나간다.
# while (i <= j)
# while(data[i] <= data[key]) #pivot보다 큰 값을 만날때까지
# i++
# while(data[j] >= data[key] && j > dividedStart) #pivot보다 작은 값을 만날때까지, 단 비교는 부분집합의 첫째 index까지(하한선 설정)
# j--

##엇갈린 상태면 pivot값과 end index value를 바꾼다.
# if( i > j)
# temp = data[j]
# data[j] = data[key]
# data[key] = temp

##엇갈리지 않은 상태면 위에서 구한 두 값을 바꾼다.
# else
# temp = data[j]
# data[j] = data[i]
# data[i] = temp

##위 알고리즘을 통해 분할된 왼쪽, 오른쪽 부분집합에 대해 각각 퀵정렬을 재귀함수처럼 다시 진행한다.
# quickSort(data, dividedStart, j-1)
# quickSort(data, j+1, dividedFianl)

4-6. 전체 코드

def quickSort(array, dividedstart, dividedfianl):
    if (dividedstart >= dividedfianl):
        return
    key = dividedstart
    i = dividedstart + 1
    j = dividedfianl

    while i <= j:
        while i <= dividedfianl and array[i] <= array[key]:
            i = i + 1
        while j > dividedstart and array[j] >= array[key]:
            j = j - 1

        # 엇갈리면 pivot값과 작은 값을 교체(현재 오름차순 정렬중)
        if i > j:
            temp = array[j]
            array[j] = array[key]
            array[key] = temp
        # 엇갈리지 않았다면 해당 data들만 교체
        else:
            temp = array[j]
            array[j] = array[i]
            array[i] = temp

    quickSort(array, dividedstart, j - 1)
    quickSort(array, j + 1, dividedfianl)


quickSort(array, 0, arrayLength - 1)
print(array)

0개의 댓글