[필기,면접] 정렬

이번에는 자료구조와 알고리즘 및 프로그래밍언어를 배우는데 있어 기본으로 많이 나오는 정렬에 대해 간단하게 알아보자

먼저, 정렬을 할때 다음과 같은 조건을 따지고 어떤 정렬을 쓰며 좋을지 생각해야한다.

정렬 -->     1. 데이터양 

                    2. 데이터와 메모리 - 데이터가 메모리에 있어야 효율적

                    3. 데이터가 정렬된 정도 - 방법에 따라 다름

                    4. 필요한 추가 메모리 양 - 원소를 바꾸는 방식으로 가능한지

                    5. 상대위치 보존여부 : 안정정렬

*안정정렬 : 동일한 값에 대해 기존의 순서유지

최적의 정렬이란 : 정렬된 데이터, 데이터의 크기, 중복된 키값을 따지며 최적의 정렬을 선택해야한다.

정렬 알고리즘은 최악기준 O(nlogn)보다 빠를수 없다.

선택정렬 : 첫 원소부터 가장 작은 값을 첫 인덱스와 교환 ~~~~~ 끝까지 반복

                    O(n^2), 불안정정렬

                    맞바꾸는 횟수는 O(n)이기 때문에 복사연산이 느린경우에 적합

삽입정렬 : 카드를 정렬하듯, 한번에 한원소씩 이미 정렬된 다른 원소들과 비교

                    정렬되어있을때, O(n), 최악은 O(n^2), 안정정렬

                    이미 정렬된 데이터집합에 대해 매우 효율적

퀵정렬 : 피벗을 기준으로 2개의 부분집합으로 나눔, 더이상 쪼갤 수 없을때까지 작업을 반복

                 불안정 정렬, 최악의 경우 O(n^2), 피벗이 최소나 최대값이라면 , 평균O(nlogn), 

머지소트 - 데이터를 둘이상의 부분집합으로 분리 후 각 부분집합을 정렬한 다음 다시 합치는 방식

                    데이터집합이 메모리에 한번에 올리기에 너무 클때 쓰기 좋음, 최고,최악 시간 : O(nlogn)

                    다만, O(n)수준의 메모리가 추가로 필요하다.

이외에도 쉘 정렬, 기수정렬, 버블정렬 등이 있으며 자세한 내용을 찾아보는 것도 무방하다고 생각한다.

필자의 경험으로는 시간복잡도가 다른 알고있는 정렬을 모두 나열하고 그 중, 몇가지를 설명하며 퀵 정렬의 동작에 대해 질문을 받았었다.

퀵정렬의 코드를 보고 이해해보면 좋을 것 같다.

#include <iostream>
#include <stdio.h>
#include<algorithm>
#include <string>
using namespace std;
 
 
int Data[10] = { 29,23,1,47,8,21,4,95,11,10 };
 
void sor(int l, int r){
    if (l >= r) return; // 없으면 R값이 음수대로 무한히 작아짐
    int p, L , R;
    p = l;
    L = p + 1;
    R = r;
    // 피벗을 항상 왼쪽으로 시작
    while (L <= R) {
        while (L <= r && Data[L] <= Data[p]) {//인덱스 범위와 피벗보다 큰값 만날떄까지
            L++;
        }
        while (R > l && Data[R] >= Data[p]) {//인덱스 범위와 피벗보다 작은값 만날때까지
            R--;
        }
        //printf("%d  %d   %d  \n",p, Data[L], Data[R]);
        if (L > R) swap(Data[p], Data[R]); // L이 R을 거쳐가면 R번쨰와 피벗값 교환
        else swap(Data[L], Data[R]); //각 값 스왑
        
    }
    for (int i = 0; i < 10; i++) {
        printf("%d ", Data[i]);
    }
    printf("\n");
    sor(l, R - 1);   //작은쪽 분할
    sor(R + 1, r);   //큰쪽 분할
}
 
int main()
{
    sor(0, 9);
    return 0;
}