📝계속 추가할 예정

📌정렬

📍정의

n개의 숫자가 입력으로 주어졌을 때, 이를 사용자가 지정한 기준에 맞게 정렬하여 출력하는 알고리즘이다.

정렬정의 참고 사이트

📍시간 복잡도(추가 예정)

Big O

📌버블정렬

📍정의

1️⃣ 배열의 2개의 아이템을 선택한 후 비교
2️⃣ 왼쪽이 오른쪽보다 클 경우, 교환함
3️⃣ 오른쪽으로 이동해서 해당 프로세스를 반복

📍시간복잡도

O(n^2)

📍구현

#include <iostream>

using namespace std;

int main(void)
{
    int arr[5] = {5,4,3,2,1};
    int swap;

    //버블정렬: 오름차순 정렬
    for(int i=0; i<4; i++){
    //1번 회전할 때마다 맨 끝에 가장 큰 수가 가게됨. 
    //그걸 맨 앞까지 하기 위해서 총 4번의 사이클이 필요함.
    //어차피 [1] 자리까지만 정해지면 [0]은 마지막 하나로 자동으로 정해지기 때문에 굳이 5번 할 필요가 없음. 
    
        for(int z=0; z<4; z++){
        //4까지 하는 이유는 밑의 코드를 보면 z+1이 존재하므로 [3]까지만 설정하면 [4]까지 비교가 가능하게 됨.
            if(arr[z] > arr[z+1]){
                swap = arr[z];
                arr[z] = arr[z+1];
                arr[z+1] = swap;
            }
        }
    }

    for(int i=0; i<5; i++){
        cout << arr[i] << endl;
    }  

    return 0;
}

📌선택정렬

📍정의

1️⃣ 전체 아이템 중에서 첫 번째에 위치한 아이템의 인덱스를 변수에 저장
2️⃣ 탐색하면서 전체 아이템 중에서 가장 작은 아이템의 위치의 인덱스를 변수에 저장
3️⃣ 가장 작은 숫자를 첫 번째 아이템과 바꿈.(임시보관 할 변수가 필요함)
4️⃣ 그 다음 사이클을 시작할 때, 정렬되지 않은 부분 중에서 가장 작은 숫자를 찾음.

📍시간복잡도

O(n^2)

📍구현

#include <iostream>

using namespace std;

int main(void)
{
    int arr[5] = {5,4,3,2,1};
    int size = 5;
    int swap;
    int min_index;  //가장 작은 값을 가진 요소의 인덱스값을 저장할 변수 선언

    //선택정렬: 오름차순 정렬
    for(int i=0; i<(size-1); i++){
    //배열의 [0]부터 수를 정렬시키기 위한 반복문: 가장 작은 값의 위치를 나타냄.
        min_index = i;
    /*
    한 번 회전할 때마다 정렬되지 않은 부분의 맨 앞에 가장 작은 숫자가 위치해야함. 
    그것을 맨 뒤까지 하기 위해서는 사실 배열크기만큼 반복해야하는 것이 맞음.
    그러나 (배열크기-1)까지만 반복해도 맨 뒤의 앞까지는 정렬되었으면 맨 뒤는 자동으로 가장 큰 수가 위치함.
    그래서 굳이 배열크기만큼 할 필요가 없음. 
    */
        for(int z=i+1; z<5; z++){
        //(i+1)부터 하는 이유는 현재 i까지는 정렬되어있으므로 정렬되지 않은 (i+1)부터 정렬하는 것임.
       //[0]을 할 때는, 우선 [0]인덱스에 있는 수가 제일 작다고 가정한 것임.
            if(arr[min_index] > arr[z]){
                min_index = z;
            }
            //현재 가장 작은 값이 있다고 가정한 위치의 인덱스의 요소보다 더 작은 값이 있을경우 인덱스 값을 더 작은 값의 인덱스로 교체함.
        }
		
        //swap이라는 임시로 수를 보관할 변수가 필요함: 그렇지 않고 두 개의 변수를 체인지 할 경우 한 값이 잃어버리게 되어 두 변수 값이 동일해짐.
        swap = arr[i];           //우선, 정렬된 값이 위치할 인덱스를 가진 값을 swap에 보관함. 
        arr[i] = arr[min_index]; //정렬된 값을 알맞은 위치로 옮김.
        arr[min_index] = swap;   //정렬된 값이 있던 위치에 swap에 보관된 값을 넣음
        //이로써 정렬된 값과, 현재 i인덱스에 있던 값이 교환됨.

    }
    
	//배열결과 출력문
    for(int i=0; i<5; i++){
        cout << arr[i] << endl;
    }  

    return 0;
}

삽입정렬

📍정의

1️⃣ [1]짜리에 있는 아이템을 왼쪽과 비교
2️⃣ 왼쪽보다 작을 경우 왼쪽과 swap
3️⃣ 바꾼 후에도 왼쪽 끝까지 비교하여 작을 경우에만 swap
4️⃣ 끝까지 반복

📍시간복잡도:

O(n^2)

📍구현

//삽입정렬
#include <iostream>
using namespace std;

int main(void)
{   
    
    int arr[5] = {8,5,6,2,4};
    //[1]탐색: 85624 -> 58624
    //[2]탐색: 58624 -> 56824 -> 56824
    //[3]탐색: 56824 -> 56284 -> 52684 -> 25684
    //[4]탐색: 25684 -> 25648 -> 25468 -> 24568 -> 24568

    int key,i,z;
    
    //오름차순 정렬
    for(i=1;i<5;i++){
    //삽입정렬은 인덱스 [1]부터 조사하기 때문이다.
        key = arr[i];
        for(z=(i-1);(z>=0 && arr[z]>key);z--){
        //삽입정렬은 key가 주어졌다면 그 key의 왼쪽을 역순으로 조사하기 때문에 key보다 하나 작은 값을 인덱스로 설정
        //역순으로 진행하다보니 마지막 인덱스는 0이 될 것임. 그러다보니 0보다 크거나 작아야함.
        //z>=0 && arr[z]>key 를 동시에 파악하는 이유는 삽입정렬에선  key앞에 있는 것은 이미 정렬이 돼있기 때문에 
        //key보다 하나 작은 인덱스 값이 key보다 크지 않을 경우는 어차피 그 앞에 있는 것도 key보다 큰 값이 없으므로 끝까지 비교할 필요가 없음. 
            arr[z+1] = arr[z];
            }

            arr[z+1] = key;
            //z가 -1되어있으므로 그것보다 +1해야지 위치를 찾을 수 있음. 
            //key가 arr[3]일 때,
            //z=2, arr[2]>key -> 56884
            //z=1, arr[1]>key -> 56684
            //z=0, arr[0]>key -> 55684
            //z=-1,           -> 25684
            //원래 key자리에서부터 역순으로 한 자리씩 key값이랑만 비교하면 되고, 그때 key가 그 자리의 값보다 작으면 key가 그 자리고 그 자리는 key 자리에 들어가야함.
            //근데 여기서 key값은 저장되어있으므로 굳이 자리를 바꾸진 않고 그냥 key 자리(본인 위치보다 한 자리 위의 인덱스]에 그 값을 넣으면 되는 것임.
            //삽입정렬은 이미 key앞에는 정렬되어있기 때문에. 
        }

    for(int i=0;i<5;i++){
        cout << arr[i] << " " ;
    }

    return 0;
}

셸정렬

📍정의

1️⃣
2️⃣
3️⃣
4️⃣

📍시간복잡도:

O(n^2)

📍구현

코드를 입력하세요

퀵 정렬

📍정의

1️⃣
2️⃣
3️⃣
4️⃣

📍시간복잡도:

O(n^2)

📍구현

코드를 입력하세요

힙 정렬

📍정의

1️⃣
2️⃣
3️⃣
4️⃣

📍시간복잡도:

O(n^2)

📍구현

코드를 입력하세요

병합정렬

📍정의

1️⃣
2️⃣
3️⃣
4️⃣

📍시간복잡도:

O(n^2)

📍구현

코드를 입력하세요