Do it! 알고리즘 코딩테스트 | 2. 정렬 - 버블 정렬 | 015 수 정렬하기 1

문제 정보 백준 2750번 수 정렬하기 https://www.acmicpc.net/problem/2750

 

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1 

5
5
2
3
4
1

예제 출력 1 

1
2
3
4
5

 

자료구조가 끝나고 정렬을 시작 했다

 

정렬에는 여러 방법이 있지만 대표적인 정렬 6가지가 있다

 

버블 정렬	인접 요소 비교	O(n^2)
선택 정렬	최대, 최솟값 선택	O(n^2)
삽입 정렬	적절한 위치 탐색 후 삽입	O(n^2)
퀵 정렬	pivot 값을 기준으로 정렬	O(nlogn)
병합 정렬	부분 집합으로 나누어 병합	O(nlogn)
기수 정렬	데이터의 자릿수 비교	O(n)

 

 

//내 코드
#include<iostream>
#define INT(t) int n, a[t]
#define F(i, t, n) for(int i=t; i<n; i++)
#define I(n) cin >> n
#define O(n) cout << n << endl;
#define SWAP(a, b) do { int t = (a); (a) = (b); (b) = t; } while(0)
#define IF(a, b) if(a > b)
using namespace std;
int main(){
    INT(1000);
    I(n);
    F(i, 0, n)
    I(a[i]);
    F(i, 0, n)
    F(j, 0, n-i-1)
    IF(a[j], a[j+1])
    SWAP(a[j], a[j+1]);
    F(i, 0, n)
    O(a[i]);
}
//define 연습해 본다고 만든 코드라 가독성은 떨어짐.. 그냥 재밌어서 해봄

 

//정답 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;
    vector<int> A(N, 0);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
  
    for (int i = 0; i < N - 1; i++) {
        for (int j = 0; j < N - 1 - i; j++) {
            if (A[j] > A[j + 1]) {
                int temp = A[j];
                A[j] = A[j + 1];
                A[j + 1] = temp;
            }
        }
    }

    for (int i = 0; i < N; i++) {
        cout << A[i] << "\n";
    }
}

 

버블 정렬은 가장 간단한 정렬 코드이다. 시간 복잡도가 O(n^2)로 효율적이진 못하지만 많은 곳에서 유용하게 쓰인다.

 

버블 정렬의 원리는 인접 인덱스의 대소관계를 비교하며 SWAP 해준다.

 

for (int i = 0; i < N - 1; i++) {
    for (int j = 0; j < N - 1 - i; j++) {
        if (A[j] > A[j + 1]) {
            int temp = A[j];
            A[j] = A[j + 1];
            A[j + 1] = temp;
        }
    }
}

 

중첩 반복문을 사용하여 모든 배열을 탐색한다.

i는 0부터 N-2까지(맨 마지막 인덱스는 비교할 뒤 인덱스가 없기 때문)

j는 0부터 N-2-i까지(정렬이 진행 될 수록 맨 뒤에는 고정 자리이기 때문)

 

그리고 temp 변수를 만들어 SWAP을 진행 해준다