정렬알고리즘(선택/삽입/계수)

선택정렬

 

 가장 작은 값은 찾는다. (첫 번째 값과 두 번째 값을 비교해서 작은 값을 찾고 그 값과 3번째 값과 또 비교하고 이렇게

차례차례 비교해서 가장 앞에 가장 작은 수를 넣는다.) 무조건  모든 것을 비교해 봐야 한다. 즉 최선과 최악의 경우의 수행 시간이 같음

 

 

따라서 선택 정렬은 전체의 배열에서 최솟값을 찾아 맨 앞에 위치시키고 인덱스를 하나씩 증가시켜 그다음 작은 값을 위치시킨다. 

 

- 최선 최악 경우 시간 : 무조건 n^2

 

삽입 정렬

 

- 삽입을 이용한 정렬 알고리즘

 

- Key 값과 정렬된 리스트가 주어졌을 때, Key값을 정렬된 리스트에 알맞은 위치에 삽입

 

  key 값을  정렬된 배열에 넣으면서 정렬 배열을 하나씩 늘려가는 정렬 방식 최선과 최악의 경우가 다르다.  for문 2개가 아닌 while 문을 사용해서 이미 정렬이 되어있는 경우에는 변수의 이동이 발생하지 않아 시간이 다른 것이다.

 

선택 정렬 달리 배열 전체를 보고 정렬을 하는 것이 아닌 가장 앞쪽부터 정렬된 배열을 증가시킨다. 정렬된 배열과 key값(정렬된 배열에서 index + 1 한 값, 위에 표에서 step 1의 key는 2, step의 key는 4)을 비교하여 정렬된 배열에 추가해 배열을 늘리는 방식으로 정렬이 된다. 

 

삽입정렬 알고리즘

계수 정렬

중복된 값이 있을 경우 사용한다. 0부터 배열의 최댓값까지의 배열을 하나 만들고 여기에 배 열애 대한 정보를 넣는다

아래의 과정을 보면 된다.

 

정렬에는 여러 가지가 있고 자기에게 맞는 알고리즘을 쓰면 된다. 

만약 중복된 값이 있으면 Counting sort를 사용(전체에서 중복된 수를 세어 다른 배열을 하나 만든다. 이 배열을 나타내는 배열을 만드는 것이 이 방법이다.)

 

알고리즘을 하이브리드로 하는 것이 맞다. 숫자가 크면 quick sort를 쓰지만 이후 정렬을 하다가 점점 작아지게 되면 오히려 시간이 더 걸릴 수가 있다. 이럴 때 select나 insert sort 알고리즘을 사용하는 식으로 한다.