선택,삽입,버블정렬

 

선택정렬 (Selection Sort) 

i가 기준, j가 두번째 포문일 시, i는 당연 처음부터 돌리고 j는 i부터 돌린다.

자기자신도 비교에 포함해야됨.

어쨌든 i기준 잡고 j돌리면서 최소값과 해당 값의 인덱스를 저장해놓고, 반복문 끝낸후에 i랑 최소값이랑 스왑해주면 된다.

시간복잡도는 O(n^2). 매 카운트마다 n-1번의 비교를위한 반복문을 돌려야 하기 때문

 

 

 

삽입정렬 (Insertion Sort)

 

최선의 성능 : O(n) ->

스왑같은거 없이 비교만할 떄, 즉 값이 거의 정렬된상태로 들어왔을 때.

 

최악의 성능 : O(n^2) -> 

아예 역순으로 배열이 인풋으로 왓을 때. 비교도 n^2번해야하고 스왑도 n^2번 해야한다.

즉, O(n^2). 물론 다른것들에 비해 '무조건'해야하는건 아니기 때문에 실제로 쓰이는 경우도 약간은 있다고 한다.

(다른 정렬알고리즘의 일부분에 쓰인다던가 등등)

 

 

버블정렬 (Bubble Sort)

 

무조건 O(n^2).

비교는 무조건 i번마다 n-1번의 반복문을 돌게되고 스왑은 조건되면 하고 아니면 안한다.

 

 

int arr[1001];
int n = 0;
 
void selectionSort() // 기준잡고 뒤의것들 검사하며 제일 작은거찾아서 기준이랑 교환
{
    for (int i = 0; i < n; i++)
    {
        int minNum = arr[i];
        int minIndex = i;
 
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < minNum)
            {
                minNum = arr[j];
                minIndex = j;
            }
        }
 
        int temp = arr[i];
        arr[i] = minNum;
        arr[minIndex] = temp;
    }
}
 
void insertionSort()
{
    for (int i = 1; i < n; i++)
    {
        int rightIndex = i;
        
        for (int j = i - 1; j >= 0; j--)
        {
            if (arr[rightIndex] < arr[j])
            {
                int temp = arr[rightIndex];
                arr[rightIndex] = arr[j];
                arr[j] = temp;
                rightIndex = j;
            }
            else break;
        }
    }
}
 
void bubbleSort()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
 
    //selectionSort();
    //insertionSort();
    bubbleSort();
 
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << endl;
    }
}