[이것이 코딩 테스트다 with Python]_23_퀵정렬

220208 작성

<본 블로그는 『이것이 취업을 위한 코딩 테스트다』 의 youtube를 참고해서 공부하며 작성하였습니다>

https://www.youtube.com/watch?v=EuJSDghD4z8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=23 

 

 

 

 

 

1. 퀵 정렬

: 기준 데이터를 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸기

: 첫 번째 데이터를 기준 데이터 (PIVOT) 으로 설정

: 가장 많이 사용되는 정렬 알고리즘

 

1) 첫 번째 수가 피벗이다

2) 왼쪽에서 5보다 큰 수를 고른다

3) 오른쪽에서 5보다 작은 수를 고른다

4) 둘이 교환한다

5) 그다음 칸 왼쪽에서 더 큰 수 고른다

6) 그다음 칸 오른쪽에서 더 작은 수 고른다

....

위치가 엇갈리는 경우!!! 피벗 (5) 와 작은 데이터의 위치를 변경

그러면 피벗 (5) 를 기준으로 왼쪽은 5보다 작은 것, 오른쪽은 5보다 큰 것으로 나뉨

피벗을 기준으로 데이터 묶음을 나누느 작업을 분할이라고 함

7) 왼쪽 데이터 묶음 정렬로 수행

8) 오른쪽 데이터 묶음 정렬로 수행

.....

이런 과정 반복

 

 

 

• python

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end) :
    if start >= end :   # 원소가 1개이면 종료
        return
    pivot = start     # 피벗은 첫 번째 숫자
    left = start + 1
    right = end

    while (left <= right) : # 피벗보다 큰 데이터 찾을 때까지
        # 피벗보다 작은 데이터 찾을 때까지
        while (left <= end and array[left] <= array[pivot]) :
            left += 1
        while (right > start and array[right] >= array[pivot]) :
            right -= 1
        
        if (left > right) :   # 엇갈림
            array[right], array[pivot] = array[pivot], array[right]
        else :
            array[left], array[right] = array[right], array[left]

    # 분할 이후.. 왼쪽, 오른쪽 묶음 정렬 ㄱ ㄱ
    quick_sort(array, start, right - 1)   # 오른쪽
    quick_sort(array, right + 1, end)     # 왼쪽

quick_sort(array, 0, len(array)-1)
print(array)

• 더 쉬운 python !!!!!

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array) :
    if len(array) <= 1 : # 원소 한개 이하..
        return array

    pivot = array[0]  # 피벗 첫 번째
    tail = array[1:]  # 피벗 제외

    left_side = [x for x in tail if x <= pivot] # 분할 왼쪽
    right_side = [x for x in tail if x > pivot] # 분할 오른쪽

    # 분할 이후, 왼쪽, 오른쪽 묶음 정렬해서 전체리스트 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

• c++

#include <bits/stdc++.h>

using namespace std;

int n = 10;
int arr[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

void quickSort(int* arr, int start, int end) {
    if (start >= end) return; // 원소가 1개인 경우 종료
    int pivot = start; // 피벗은 첫 번째 원소
    int left = start + 1;
    int right = end;
    while (left <= right) {
        // 피벗보다 큰 데이터를 찾을 때까지 반복
        while (left <= end && arr[left] <= arr[pivot]) left++;
        // 피벗보다 작은 데이터를 찾을 때까지 반복
        while (right > start && arr[right] >= arr[pivot]) right--;
        // 엇갈렸다면 작은 데이터와 피벗을 교체
        if (left > right) swap(arr[pivot], arr[right]);
        // 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
        else swap(arr[left], arr[right]);
    }
    // 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quickSort(arr, start, right - 1);
    quickSort(arr, right + 1, end);
}

int main(void) {
    quickSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << ' ';
    }
}

• java

import java.util.*;

public class Main {

    public static void quickSort(int[] arr, int start, int end) {
        if (start >= end) return; // 원소가 1개인 경우 종료
        int pivot = start; // 피벗은 첫 번째 원소
        int left = start + 1;
        int right = end;
        while (left <= right) {
            // 피벗보다 큰 데이터를 찾을 때까지 반복
            while (left <= end && arr[left] <= arr[pivot]) left++;
            // 피벗보다 작은 데이터를 찾을 때까지 반복
            while (right > start && arr[right] >= arr[pivot]) right--;
            // 엇갈렸다면 작은 데이터와 피벗을 교체
            if (left > right) {
                int temp = arr[pivot];
                arr[pivot] = arr[right];
                arr[right] = temp;
            }
            // 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            else {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        // 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
        quickSort(arr, start, right - 1);
        quickSort(arr, right + 1, end);
    }

    public static void main(String[] args) {
        int n = 10;
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

        quickSort(arr, 0, n - 1);

        for(int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }

}

 

 

 

 

 

 

2. 퀵 정렬 빠른 이유

: 이상적인 경우 분할이 절반씩 일어난다면, 전체 연산 횟수로 O(NlogN)

: 너비 X 높이 = N X logN = NlogN

 

 

 

 

3. 퀵 정렬 시간 복잡도

: 평균 O(NlogN)

: 최악은 O(N^2)         이미 정렬된 배열에 대해 퀵 정렬을 하면... 매번 분할 이뤄짐..

=> O(NlogN)