알고리즘 취준

정렬 알고리즘_1

선택,삽입,버블 정렬에 대하여 알아보자

Posted by kyoungIn on March 22, 2019

정렬 알고리즘

< 선택 정렬(Selection sort) >

기본이 되는 정렬 중 하나이다. 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다. 현재 위치에 저장될 값의 크기가 작냐, 크냐에 따라서 최소 선택 정렬(오름차순으로 정렬)과 최대 선택 정렬(내림차순으로 정렬)이 있다. 일반적으로 최소 선택 정렬이 쓰인다.

로직

  1. 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째 인덱스 값과 바꿔준다.

  2. 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 인덱스 값과 바꿔준다.

  3. 위 과정을 반복하며 정렬을 수행한다.

    쉽게 말해서 모든 배열의 원소를 하나씩 기준으로 잡고 다른 모든 원소와 비교하며 작은 수를 앞으로 보내며 정렬하는 방법이다.배열이 어떻게 되어있든 전체를 모두 비교한다.

    구현은 간단하지만 매우 비효율적이다. O(N^2)의 시간복잡도를 가지고 있다. 공간 복잡도는 하나의 배열에서 하므로 O(N).

장점

  • 자료 이동 횟수가 미리 결정된다.

단점

  • 안정성을 만족하지 않는다.
  • 즉, 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include <iostream>
using namespace std;
int main(){
    int arr[5]={3,5,6,1,2};
    for(int i=0;i<4;i++){  // 0~3
        int min=i;
        for(int j=i;j<5;j++)  //i~4
            min = arr[min] > arr[j] ? j : min;
        int temp=arr[i];
        arr[i]=arr[min];
        arr[min]=temp;
    }
    for(int i=0;i<5;i++)
        cout << arr[i] << ' ';
}

<삽입 정렬(Insertion sort)>

손안의 카드를 정렬하는 방법과 유사하다. 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입한다. 새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다. 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성한다. 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.

로직

  1. 두번째 인덱스부터 시작한다.

  2. 앞 인덱스 자료들과 비교하여 삽입할 위치를 정한 뒤 자료를 뒤로 옮기고 지정한 자리에 삽입

    즉, 두번째자료는 첫번째자료와 비교, 세번째자료는 두번째,첫번째자료와 비교,,,한 뒤 그 자리에 자료를 삽입하기 위해 기존자료들을 한칸씩 뒤로 민다.

    시간복잡도는 최소 O(N), 최대 O(n^2)이므로 O(N^2)이고 공간복잡도는 하나의 배열에서 하므로 O(N)

장점

  • 안정한 정렬 방법
  • 레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다.
  • 대부분의 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.

단점

  • 비교적 많은 레코드들의 이동을 포함한다.
  • 레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <iostream>
using namespace std;
int main(){
    int arr[5]={5,4,3,1,2};
    int i,j;
    for(i=1;i<5;i++){  // 0~3
        int key=arr[i];
        for(j=i-1;j>=0;j--){  //i~4
            if(arr[j]<=key) break;
            arr[j+1]=arr[j];
        }
        arr[j+1]=key;
    }
    for(int i=0;i<5;i++)
        cout << arr[i] << ' ';
}

< 버블 정렬(Bubble sort) >

거품이 위로 올라가는 모양으로 정렬되서 버블정렬. 매번 연속된 두개의 인덱스를 비교해서,정한 기준(오름차순, 내림차순)에 따라 값을 뒤로 넘기며 정렬한다.(선택 정렬과 비슷) 오름차순 정렬할 경우 한바퀴를 돌면 최대값이 맨 끝 인덱스값으로 가있다.

1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

로직

  1. 두번째 인덱스부터 시작하여 현재 인덱스의 값과 인접한 인덱스의 값을 비교
  2. 만약 현재 값보다 크면 스왑
  3. 현재 값이 더 크면 다음 인덱스의 비교로 넘어감
  4. 이 과정을 전체배열의 크기 - 순환한 바퀴수 만큼 한다.

시간 복잡도는 O(N^2) , 공간 복잡도는 **O(N)

장점

  • 구현이 매우 간단하다.

단점

  • 순서에 맞지 않은 요소를 인접한 요소와 교환한다.
  • 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
  • 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.
  • 일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <iostream>
using namespace std;
int main(){
    int arr[5]={5,4,3,2,1};
    int i,j;
    for(i=0;i<5;i++){  
        for(j=1;j<5-i;j++){  
            if(arr[j-1] > arr[j]){
                int temp= arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=temp;
            }
        }
    }
    for(int i=0;i<5;i++)
        cout << arr[i] << ' ';
}

참고

https://hsp1116.tistory.com/33

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

FEATURED TAGS
Algorithm BOJ Programmers 취준 SWEA C++ 알고리즘 DataBase nodeJS CS OS nodeJs
FRIENDS