[Algorithm][sort] sort 개념 및 구현

I. 정렬(sort)이란? 

말 그대로 정렬이다.

우리는 코딩을 하면서 배열, 벡터 등을 사용하게 되는데

특히 알고리즘에서는 이들을 순서, 우리가 원하는 조건에 맞추어 Data를 정렬해야되는 상황이 많다.
(ex. 오름차순(1,2,3) 내림차순(3,2,1), 2차원 배열 등)

이런 정렬 알고리즘은
버블, 선택, 삽입, 합병, 힙, 퀵 등 많은 방법이 있는데,
퀵을 가장 많이 쓰고 활용되기에 이 정렬만 구현할 것이다.

이번 글에서는 다음 두 가지를 정리할 것이다.
1. Quick sort 직접구현
2. c++ STL <algorithm>속 sort() 사용법

 

---

II. Quick sort 원리 (오름차순)

- 평균 시간복잡도 O(N*Log(N))
- 분할 정복 법

기본적으로 pivot,i,j의 3개 인덱스로 각 배열의 값을 탐색하게 된다.
pivot을 기준으로 작으면 왼쪽, 크면 오른쪽에 배치를 시키는 것이다.

1. pivot(기준 인덱스) 설정
2. pivot 기준으로 작으면 왼쪽 크면 오른쪽 배치
3. 정렬 끝날 때 까지 구분된 왼쪽 오른쪽을 분할해서 반복한다.

---

이 과정을 그림으로 보자

1. pivot과 j는 처음, i는 그 다음 인덱스로 시작

1. 첫번 째 인덱스는 pivot과 j, 2번째 인덱스는 i로 시작

 

2. i와 pivot을 비교해 Arr[i] > Arr[pivot] 이다.
아무일도 일어나지 않고 다음 단계로.(i+1)

Arr[i] > Arr[pivot] 아무변화 x

 

3. i와 pivot을 비교해 Arr[i] < A[pivot] 이다.
** 이때 j를 +1 해주고 j와 i의 데이터를 스왑!

3. j+1 후 Arr[i], Arr[j] 스왑!

 

이 과정을 i가 end일 때 까지 반복하게되면...

최종 단계의 모습 (이전대비 2와 4만 바뀐상태이며 j+1됨)

 

4. 최종적으로 Arr[pivot]과 Arr[j]를 스왑한다!!

4. 최종 j위치까지 정렬

최종적으로 현재 pivot의 왼쪽에는 모두 Arr[pivot]보다 작은 수,
오른쪽에는 모두 Arr[pivot]보다 큰 수가 모여있다.

5. pivot 양쪽을 분할 정복한다.

 

---

III. Sort 구현

 

1. 위 과정을 코드로 구현하면

<hide/>
#include <stdio.h>

int Arr[6] = {3,4,1,5,2,6};

void AscendQsort (int s,int e){
    if(s>e) return; //탈출조건
    
    int pivot{s}; 
    int j{s};
    int i{j+1};
    
    int temp{0};
    
    // i가 e까지 진행하며 반복함
    for( ; i<=e ; i++){
        //만약 pivot숫자보다 작으면
    	if(Arr[pivot] >= Arr[i]){
            j++; //j 하나 증가
            
            //아래 3줄 i,j 스왑코드
            temp = Arr[j];
            Arr[j] = Arr[i];
            Arr[i] = temp;
        }
    } // 위 조건에 들지 않으면 그냥 무시
    
    //아래 3줄 pivot,j 스왑코드
    temp = Arr[j];
    Arr[j] = Arr[pivot];
    Arr[pivot] = temp;
    
    //아래 2줄 왼쪽, 오른쪽 분할정복(재귀함수)
    AscendQsort(s, j-1);
    AscendQsort(j+1,e);
    
    return;
}

int main(){
    AscendQsort(0,5);
    for(int i=0;i<6;i++) printf("%d ",Arr[i]); //1 2 3 4 5 6
    
    return 0;
}

 

2. C++ STL sort() 사용법

#include <algorithm> 헤더 필요함.

기본모습 std::sort( &Arr[0], &Arr[0+N], (UserFunction) );
UserFunction(함수포인터) 이 생략되면 자동으로 오름차순정렬된다.

사용 예제

<hide/>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> V1; //1차원 벡터
vector<vector<int>> V2; //2차원 벡터
vector<int> V2temp; // 2차원 벡터에 넣기위한 1차원벡터

int Arr1[6]; // 1차원 배열
int Arr2[6][2]; // 2차원 배열

void input() {
	// 1차원 배열에 [1,2,3,4,5,6] 넣기
	for (int i = 0; i < 6; i++) {
		V1.push_back(i);
		Arr1[i] = i;
	}

	// 2차원 배열에 [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]] 넣기
	for (int i = 0; i < 6; i++) {
		for (int j = i; j < i + 2; j++) {
			V2temp.push_back(j);
			Arr2[i][j - i] = j;
		}
		V2.push_back(V2temp);
		V2temp.clear();
	}
}

	// 1차원일 때 내림차순
	int user1Descend(int a, int b) {
		return (a > b); // 내림차순이므로 앞쪽의 a가 커야함. 이때 true 반환
	}

	// 2차원 Arr일 때 2번째 항을 기준으로 내림차순
	int user2ArrDescend(int a[2], int b[2]) {
		return (a[1] > b[1]);
	}

	// 2차원 Vec일 때 1번째 항을 기준으로 내림차순
	int user2VecDescend(vector<int> a, vector<int> b) {
		return (a[0] > b[0]);
	}

	int main() {
		input();

		sort(&Arr1[0], &Arr1[0 + 6]); //오름차순
		sort(&Arr1[0], &Arr1[0 + 6], user1Descend); // Arr 내림차순
		sort(V1.begin(), V1.end(), user1Descend); // Vec 내림차순

		//이건 잘못된 코드임! Array는 2차원이어도 주소가 연속적이기 때문.
		//sort(&Arr[0][0], &Arr[0+6][0+2],user2ArrDescend) Arr 2번째 항 기준 내림차순

		sort(V2.begin(), V2.end(), user2VecDescend); // Vec 내림차순

//람다함수 사용법
        sort(V1.begin(), V1.end(), [](int a, int b){ return a>b; } );

		printf("Print Array\n");
		for (int i = 0; i < 6; i++) {
			printf("%d ", Arr1[i]);
		}
		printf("\n");
		printf("Print Vec \n");


		for (int i = 0; i < 6; i++) {
			printf("%d ", V1[i]);
		}
		printf("\n");

		for (int i = 0; i < 6; i++) {

			for (int j = 0; j < 2; j++) {
				printf("%d ",V2[i][j]);
			}
			printf("\n");
		}

		return 0;
	}

이와같이 sort()와 user function을 정의하여 사용하면 원하는 대로 정렬할 수 있다.

내가 사용했었던 함수로는 아래 용도들이 있었다.

1차원 정렬
2차원 정렬 중 원하는 열의(j) index로 정렬
2차원 배열에서 두 수가 중복일 때 처리하여 정렬

 

---

IV. 기타 응용

대부분 정렬을 필요로 하는 문제는

- 겹치지 않게 회의실을 배정해야 하는 문제같은 Greedy문제 (어떻게 정렬하느냐가 중요)

- 정렬 이후 Search를 사용하여 해결하는 문제 (그냥 정렬만 필요함)

위와 같은 풀이과정의 도구로써 이용이 된다.