선택정렬

한 바퀴씩 돌아서 최소값을 제일 앞으로 보내면서 정렬하는 것 → O(N^2)

삽입정렬

두번째 원소부터 선택하여 앞의 원소들 사이에 삽입을 하며 정렬하는 것 → O(N^2)

버블정렬

옆에 있는 것들끼리 비교하며 1회전 → 마지막 원소에 가장 큰 숫자가 있을 것 → 반복 → O(N^2)

머지소트 (Merge Sort)

분할 정복 알고리즘 중 한 방법

→ 분할정복 알고리즘이란? 한 문제를 두 문제로 나누어 각각을 해결하고, 결과를 모아서 한 문제를 해결하는 것

• 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
• 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
• 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.

퀵소트 (Quick Sort)

분할 정복 알고리즘 중 한 방법, 매우 빠른 수행 속도, 머지소트와 다르게 비균등하게 배열을 분할

• 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
• 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.

시간복잡도는 O(nlogn)이지만, 리스트가 계속 불균형하게 나누어지는 경우 (특히, 이미 정렬된 리스트에 대하여 퀵 정렬을 실행하는 경우)엔 O(N^2)