선택 정렬, 삽입 정렬

선택정렬

내 코드

#include <iostream>
using namespace std;

int main()
{
    int arr[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8}, minNum = 21e8, minLevel = -1;
    for(int i=0; i<10; i++)
    {
        minNum = 21e8;
        minLevel = -1;
        for(int j = i; j< 10; j++)
        {
            if(minNum > arr[j])
            {
                minNum = arr[j];
                minLevel = j;
            }
        }
        int a = arr[minLevel];
        arr[minLevel] = arr[i];
        arr[i] = a;
    }
    for(int i=0; i<10; i++)
        cout << arr[i] << ' ';
    return 0;
}

교재 코드

#include <bits/stdc++.h>

using namespace std;

int n = 10;
int arr[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

int main(void) {
    for (int i = 0; i < n; i++) {
        int min_index = i; // 가장 작은 원소의 인덱스 
        for (int j = i + 1; j < n; j++) {
            if (arr[min_index] > arr[j]) {
                min_index = j;
            }
        }
        swap(arr[i], arr[min_index]); // 스와프
    }
    for(int i = 0; i < n; i++) {
        cout << arr[i] << ' ';
    }
}

 

교재 코드는 가장 작은 원소의 인덱스의 값을 최솟값으로 놓고 시작하여 i+1로 시작하지만 난 i부터 값을 비교하여 구한다는 차이가 있지만 사실상 같은 풀이이다. 오히려 나는 minNum에 값을 저장하여 메모리와 시간을 낭비하였다. 

 

삽입정렬

내 코드

#include <iostream>
using namespace std;

int main()
{
    int arr[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
    
    for(int i= 1; i<10; i++)
    {
        for(int j= i; j> 0; j--)
        {
            if(arr[j] > arr[j-1]) break;
            swap(arr[j], arr[j-1]);
        }
    }
    for(int i=0; i<10; i++)
        cout << arr[i] << ' ';
    return 0;
}

교재 코드

#include <bits/stdc++.h>

using namespace std;

int n = 10;
int arr[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

int main(void) {
    for (int i = 1; i < n; i++) {
        // 인덱스 i부터 1까지 감소하며 반복하는 문법
        for (int j = i; j > 0; j--) {
            // 한 칸씩 왼쪽으로 이동
            if (arr[j] < arr[j - 1]) {
                swap(arr[j], arr[j - 1]);
            }
            // 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            else break;
        }
    }
    for(int i = 0; i < n; i++) {
        cout << arr[i] << ' ';
    }
}

바로 앞의 값보다 작지 않으면 더 이상 살펴보지 않고 그 자리에 삽입하므로 정렬이 되어 있지 않은 경우 O(N^2)이지만 정렬이 된 최선의 경우 O(N)이다. 따라서 거의 정렬이 된 상태에서 입력이 주어진다면 여타 정렬보다 삽입 정렬을 사용하는 것이 좋다.