[Algorithm]선택정렬 삽입정렬 버블정렬

정렬의 이해 및 구현 By java

정렬은 내가 가진 데이터를 오름차순 혹은 내림차순으로 재배열 해주는 것을 의미한다.

데이터의 정렬 방법에는 3가지가 있다.

Selection-Sort(선택정렬) / Insertion-Sort(삽입정렬) / Bubble-Sort(버블정렬)

세 정렬 모두 O(n^2) 의 시간복잡도를 가지지만, 각각 정렬 방식의 차이가 있다.

모든 예제는 오름차순을 기준으로 서술하였다.

< Selection Sort ( 선택정렬 ) >

선택정렬의 정렬그래프는 다음과 같다.

Selection Sort [ 출처 : wikipedia ]

선택정렬은 전체 값 중 최소값을 찾아 앞의 index로 바꿔준다.

arr[0]의 값을 넣을 때 전체의 최소값을 찾고 arr[0]과 값을 바꿔준다.

그리고 arr[1]로 넘어와 arr[0]의 값을 제외한 나머지 데이터 중 최소값을 찾아 arr[1]에 넣어준다.

이것을 코드로 구현하면 다음과 같다.

SelectionSort [java]

<Insertion Sort ( 삽입정렬 ) >

삽입정렬의 정렬그래프는 다음과 같다.

Insertion Sort [ 출처 : wikipedia ]

선택정렬이 값을 넣을 위치를 정해놓고(arr[0]부터 arr[1], arr[2]... 순으로) 데이터를 비교했다면,

삽입정렬은 데이터를 기준으로 데이터가 자신의 위치를 찾아가도록 한다.

코드를 보며 조금더 분명하게 이해해보자.

Insertion Sort [java]

 tmp의 값은 자신의 위치를 찾아야할 데이터의 값이다.

tmp의 index보다 앞에 있는 값들과 대소 비교를 하여 위치를 찾기 때문에

while문을 이용해 0~ i-1의 배열값들과 전부 비교를 한다.

while문 탈출 조건으로는 index가 0일 경우, 이는 곧 tmp의 값이 최소값이라는 것을 의미한다.

그리고 앞의 index로 이동하면서 그 값이 tmp보다 클 때는 tmp의 위치를 찾았다는 것이므로

while문을 탈출한다.

while문 안에서는 

tmp의 값이 들어갈 위치를 비어야 하므로 기존의 값들을 한 칸씩 뒤로 밀어내고, 

arr[index+1] = arr[index];

비교할 배열의 index를 바꿔준다.

index--;

while 문을 빠져나오면 arr[index+1]는 tmp가 들어가야할 위치이므로 tmp의 값을 넣어준다.

*while문을 탈출할 때 index-- 해서 나오기 때문에 index+1을 해줘야한다.

<Bubble Sort ( 버블정렬 ) >

버블정렬의 정렬그래프는 다음과 같다.

Bubble Sort [ 출처 : wikipedia ]

버블정렬은 arr[index-1]의 값과 arr[index]값을 비교하면서

arr[index-1]의 값이 더 크면 일단 바꾸고 본다.

그렇게 전체 배열들을 바꿔가다보면 큰 값이 뒤로 밀려나면서 쌓이게 된다.

버블정렬의 코드는 다음과 같다.

Bubble Sort [java]

선택정렬과 삽입정렬보다 코드가 훨씬 간단해 더 많이 사용된다고 한다.

주의해서 봐야할 부분은 주석을 넣은 두 번째 for문이다.

배열의 범위를 벗어나면 안되므로 j는 1부터 시작하고,

뒤로 밀려난 값들을 다시 비교하면 안되므로 arr.length - i 를 해준다.

그 안에서 arr[index-1]의 값이 더 클 경우 바꾸면서 for문을 진행하면 된다.