(알고리즘) Quick Sort

📌저번에 Merge Sort 에 이어 Quick Sor를 적어보려구 한다.

🚀Quick Sort

Quick Sort은 Merge Sort 과 비슷하게 분할정복(Divide and Conquer) 알고리즘이다. 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다
🪄 Divide(분할) : 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
🪄 Conquer(정복) : 부분 배열을 정렬한다.
🪄 Merging(결합) : 부분 배열을 정렬한다.

🚀 Pivot 선정 방법

• 전체를 다 비교해서 중간값 찾기
• 랜덤하게 선정
• 세개의 숫자의 중앙값으로 선정하는 방법 (Approximately sampling)

  가장 왼쪽 숫자, 중앙 숫자, 가장 오른쪽 숫자 중에서 중간값으로 피봇을 선정

🚀Quick Sort 개념

Quick Sort는 Merge Sort와 비슷하지만 다른 방식으로 수행한다.
리스트안에서 임의의 요소를 선정한다. 이러한 요소는 Pivot이라고 부른다.

• Pivot 기준으로 작은 숫자들은 왼쪽
• Pivot 기준으로 큰 숫자들은 오른쪽
  균등하게 나뉘어서 Pivot을 제외하고 다시 정렬해준다.

💻코드

#include<stdio.h>
#include <stdlib.h>
#define MAXSIZE 12

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
int pivot(int list[], int start, int finish ){
    int pi = list[(start+finish) / 2]; // 피봇 설정  (가운데)
        while(start<=finish){  //  start 가 finish 보다 오른쪽에 있을때까지 반복
            while(pi>list[start]){  // start가 피봇보다 큰 값을 만날때까지 반복
                start++;
            }
            while(pi<list[finish]){  // 위와 동일 하게 finish 가 피봇보다 작을때 까지 반복
                finish--;
            }
            if(start <= finish){ //start에 있는 인덱스가  finish 보다 왼쪽에 있다면 위치변경
                swap(&list[start],&list[finish]);
                start++; // start 오른쪽 한칸 , finish 왼쪽으로 한칸간다
                finish--;
            }
     
    }
       return start;
}


void Quick_Sort(int list[], int start, int finish ){

    if(start<finish){
        int p = pivot(list , start, finish); //피봇설정
        Quick_Sort(list,start,p-1);  //왼쪽 배열 재귀적 반복
        Quick_Sort(list, p , finish); //오른쪽 배열 재귀적 반복
    }
        printf("Quick Sort중\n"); 
        for(int i=0; i<MAXSIZE; i++){
        printf("%d ", list[i]);
        }
}

void main() { 
    int list[MAXSIZE] = {6,3,11,9,12,2,8,15,18,10,7,14};
    printf("Quick Sort전\n");
        for(int i=0; i<MAXSIZE; i++){
    printf("%d ", list[i]);
        }
    printf("\n");
    Quick_Sort(list,0,MAXSIZE-1);
    printf("\n");
    printf("Quick Sort후 \n");
        for(int i=0; i<MAXSIZE; i++){
    printf("%d ", list[i]);
}
}

💻 출력

🙋🏻‍♂️ 느낀점

수업시간에 이론으로 배우고 직접 실습해보니 엄청 어렵다... 또한 아직 시간복잡도를 개념이 아직 미숙해서 조금더 성장해서 다시 시간복잡도 개념까지 수정할 예정이다. 이렇게 실습을 하고 기록을 하니깐 색다른 경험이다 🥹🥹