[#2750] 수 정렬하기

1. 거품 정렬 (bubble sort)

#include <iostream>
#include <vector>
 
using namespace std;
 
//거품 정렬
int main() {
    int n;
    cin >> n;
 
    vector<int> number(n, 0);
 
    for (int i = 0; i < n; i++) {
        cin >> number[i];
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (number[j] > number[j + 1]) {
                int temp = number[j + 1];
                number[j + 1] = number[j];
                number[j] = temp;
            }
        }
    }
 
    for (int i = 0; i < n; i++) {
        cout << number[i] << "\n";
    }
    return 0;
}

 

 

2. 삽입 정렬

#include <iostream>
#include <vector>
 
using namespace std;
 
//삽입 정렬
int main() {
    int n;
    cin >> n;
 
    vector<int> number(n, 1001);
 
    for (int i = 0; i < n; i++) {
        cin >> number[i];
    }
 
    for (int i = 1; i < n; i++) {
        int index = i;
        while (index > 0) {
            if (number[index] < number[index - 1]) {
                int temp = number[index - 1];
                number[index - 1] = number[index];
                number[index] = temp;
                index--;
            }
            else {
                break;
            }
        }
    }
 
    for (int i = 0; i < n; i++) {
        cout << number[i] << "\n";
    }
 
    return 0;
}

 

두번째 원소[1] 부터 앞 부분 원소들한테 크기 비교하면서 알맞은 자리에 끼워넣기

앞부분 원소들은 다 정렬되어있음. 끼워질때 밀려야함

 

 

3. 선택 정렬

#include <iostream>
#include <vector>
 
using namespace std;
 
//선택 정렬
int main() {
    int n;
    cin >> n;
 
    vector<int> number(n, 1001);
 
    for (int i = 0; i < n; i++) {
        cin >> number[i];
    }
 
    for (int i = 0; i < n-1; i++) {  
        //n-1까지만 돌리면 됨. 왜냐면 다른 반복문에서 다음 숫자와 비교해기때문에 마지막 숫자는 알아서 정렬됨.
        int minIndex = i;  //i번째 원소가 최소 원소라고 생각하고 비교 시작
 
        for (int j = i+1; j < n; j++) {
            if (number[minIndex] > number[j]) {
                minIndex = j;
            }
        }
 
        int temp = number[minIndex];
        number[minIndex] = number[i];
        number[i] = temp;
    }
 
    for (int i = 0; i < n; i++) {
        cout << number[i] << "\n";
    }
 
    return 0;
}

 

가장 작은 원소 찾아서 i번째 원소랑 바꾸기