정렬 아록리즘
알고리즘이란
문제를 해결하기 위한 ㅇ리련의 명령이나 반복되는 절차.
정렬 알고리즘
정렬을 하는 이유 : 탐색을 쉽게 하기 위해서.
1. 버블 정렬 ( Bubble sort)
정렬의 대상을 줄여나간다.
데이터가 어떠한 방식으로 정렬되었는지와 상관 없이 항상 같은 횟수의 비교 연산을 거친다.
n(n-1) / 2 의 비교 연산으로 정렬 알고리즘을 수행. (가우스 초식을 연상 n-1 + ... + 1)
삽입 정렬 (Insertion Sort)
정렬으리 대상을 늘려나간다.
데이터가 이미 정렬된 상태라면 비교 연산을 거치지 않는다. ( 데이터의 정렬 상태에 따라 연산 횟수는 유동적)
버블 정렬과 반대로 정렬 대상을 늘리면서 연산하므로 가우스 초식의 역을 연상한다. ( 1 + 2 + .. + n-1)
다만 데이터 정렬 상태에 따라 최선의 경우와 최악의 경우로 나뉘므로 이것의 평균을 구한다면 n^2 + n -1 / 2 이다.
즉, 버블 정렬에 비해 삽입 정렬이 평균적으로 더 나은 성능을 보인다. (그러므로 크기가 작은 데이터 집합을 정렬한다면 버블 정렬보다는 삽입 정렬을 사용하는 편이 효율적이다.)
퀵 정렬 (Quick Sort)
분할 정복 (Divide and Conquer)에 기반한 알고리즘
분할 정복 알고리즘이란... 전쟁 전략에서 중 하나인 분할 정복에 기반한 알고리즘이다. 적군의 전체를 공략하는 대신, 전체를 구성하는 구성 요소들을 나누어 잘게 쪼개진 적을 공략하는 전법인 분할 정복처럼 전체를 구성하는 구성 요소들을 나누어 연산을 수행하는 알고리즘인 것이다.
1. 데이터 집합 내에서 임으의 기준 요소를 선택하고, 기준 요소보다 작은 요소들은 순서에 관계없이 무조건 기준 요소의 왼편에, 큰 값은 오른편에 위치시킵니다.
2. 기준 요소 왼편에는 기준 요소보다 작은 요소들이 모여 있고 오른편에는 큰 요소들이 모여있다. 나누어진 데이터 집합ㅇ들을 다시 1에서와 같이 임의의 기준 요소를 선택하고 같은 방법으로 데이터 집합을 분할한다.
3. 이러한 과정을 더이상 데이터 집합을 나눌 수 없을 때까지 반복하면 정렬된 데이터 집합이 만들어진다.