Sorting - (1)

종류

Bubble Sort:
데이터의 인접 요소끼리 비교, swap방식을 통해 정렬하는 방식
Selection Sort:
대상에서 가장 크거나 작은 데이터를 찾아 선택하면서 정렬하는 방식
Selection Sort:
대상을 선택해 정렬된 영역에서 적절한 위치를 찾아가며 삽입하여 정렬하는 방식
Quick Sort:
pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식
Merge Sort:
이미 정렬된 부분 집합들을 효율적으로 병합하여 전체를 정렬하는 방식
Radix Sort:
데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식

Bubble Sort

결국 최종적으로 배열의 가장 끝부분부터 정렬된다고 생각하면 된다.

수 정렬하기 (백준 2750번, 시간 제한: 2초)

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

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

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

입력 예시
5
5
2
3
4
1

출력 예시
1
2
3
4
5

코드 예시

import sys
input=sys.stdin.readline
n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
print(a)
for i in range(n):
    for j in range(n-i-1):
        if a[j+1]<a[j]:
            temp=a[j]
            a[j]=a[j+1]
            a[j+1]=temp
for i in range(n):
    print(a[i])

N이 최대 1000이기 때문에 시간복잡도는 O(n^2) 으로도 충분하다. 즉 이번에는 bubble sort 로 짜보았다.
우리가 알고 있는 것처럼 서로 인접한 두 원소를 비교하여 sorting 한다.

이 과정을 하게 되면 가장 끝 원소는 가장 큰 원소가 들어가게 되므로 굳이 해당 구간까지 계속해서 반복문을 돌릴 이유는 없다.