참된코딩

삽입정렬 (Insertion sort)

리스트를 가상으로 왼쪽과 오른쪽 리스트로 구분하자.

왼쪽은 정렬이 되어있고, 오른쪽은 정렬해야될 값이 들어있다.

오른쪽 리스트에 첫 번째 값이 왼쪽 리스트의 어느 위치에 삽입되어야 하는가를 판단한 후 제 위치에 삽입한다.

이 경우, 삽입될 위치로부터 오른쪽에 있는 값들을 한 칸씩 오른쪽으로 이동시킨다.

임의의 값을 정렬해보자.

정렬의 순서는 오름차순이다.

※ 유의사항

- 삽입정렬은 영역을 정하고 그 영역 안에서의 순서를 정해 이동하는 방식이다.

- value : 현재 기준이 되는 값. 또는 값의 임시 저장소라고 생각하면 된다.

시작 : 7 3 9 4 1

1).

 value  : 3

              ↓

인덱스 :   0 1 2 3 4

   값    : [7 3] 9 4 1 

3을 기준으로 7을 비교한다.

if( 3 < 7 ) ? 참.   

현재 검사하고 있는 범위( [ ] ) 안에서 각 숫자들을 한 칸씩 당겨주어야 하므로.

1번째 인덱스에 0번째 인덱스 값을 넣는다.

      ↓

- [ 7 7 ] 9 4 1 

다음은 비교할 값이 없으므로 현재 인덱스에 value가 가진 값을 대입한다.

    ↓

- [ 3 7 ] 9 4 1 

2).

value  : 9

               ↓

인덱스 :  0 1 2   3 4

인덱스: [ 3 7 9 ] 4 1    

if( 9 < 7 ) ? 거짓.

if문의 조건이 충족되지 않으므로 다음으로 넘어간다.

3).

 value  : 4

                   ↓

인덱스 :    0 1 2 3   4

   값    : [ 3 7 9 4 ] 1 

if( 4 < 9 ) ? 참

1. 숫자들을 뒤로 한 칸씩 당긴다.

2. value의 값과 당길 숫자들과 비교한다.

3. 당길 숫자가 value의 값보다 더 작다면 현재 인덱스의 + 1칸에 value값을 대입한다.

        ↓

- [ 3 7 9 4 ] 1  - if( 4 < 9 ) ? 참

=>[ 3 7 9 9 ] 1

      ↓

- [ 3 7 9 9 ] 1  - if( 4 < 7 ) ? 참

=>[ 3 7 7 9 ] 1 

4).

 value  : 1

                      ↓

인덱스 :    0 1 2 3 4

   값    : [ 7 3 4 9 1 ]

if( 1 < 9 ) ? 참

1. 숫자들을 뒤로 한 칸씩 당긴다.

2. value의 값과 당길 숫자들과 비교한다.

3. 당길 숫자가 value의 값보다 더 작다면 현재 인덱스의 + 1칸에 value값을 대입한다.

        ↓

-   [ 3 4 7 9 9 ]  - if( 1 < 4 ) ? 참

=>  [ 3 4 4 7 9 ]

      ↓

-   [ 3 4 7 9 9 ]  - if( 1 < 3 ) ? 참

=>  [ 3 3 4 7 9 ]

더이상 검사할 인덱스가 없으므로 현재 인덱스에 vaule를 대입.

=> [ 1 3 4 7 9 ]

Code

결과

▷ 선택정렬(Selection sort)

선택정렬은 가장 작은 값을 선택하여 그 값을 나열하는 과정을 반복하는 간단한 정렬 알고리즘이다.

배열에 존재하는 값중 가장 작은 값을 찾아서 첫 번째에 위치하는 값과 교환한다.

다음은 첫 번째를 제외한 나머지 값들 중 가장 작은 값을 찾아서 두 번째 위치하는 값과 교환한다.

이렇게 모든 배열이 정렬될 때 까지 게속한다.

임의의 값을 정렬해보자.

정렬의 순서는 오름차순이다.

▷ 정렬방법.

1. 처음 시작 시 가장 작은 값이 어떤 위치에 있는지 모르기 때문에 첫 번째 위치에 있는 값을 가장 작은 값으로 설정한다.

2. 값의 위치를 하나씩 옮기면서 가장 작은 값으로 설정했던 값과 비교한다.

3. 처음 설정했던 값보다 작은 값이 나오면 그 값을 가장 작은 값으로 설정하고 모든 값의 비교가 끝날때 까지 비교를 게속한다.

4. 모든 비교가 끝났으면 가장 작은 값과 첫 번째 값을 교환한다.

5. 첫 번째 값을 제외하고 1~4번의 과정을 반복한다.

※ 유의사항. 

- Min : 제일 작은 값.

- Index : 값의 인덱스.

- 제일 작은 값이 어떤 값인지 모른다고 가정한다.

- 처음 시작 시 0번째 인덱스를 제일 작은 값이라고 설정한다.

시작 : 5, 7, 3, 4, 9, 1

1).

- Min : 5

- Index : 0

Index : 0 [1] 2 3 4 5

value : 5 [7] 3 4 9 1

2).

- Min : 3

- Index : 2

Index : 0 1 [2] 3 4 5

value : 5 7 [3] 4 9 1

값과 인덱스를 기억.

3).

- Min : 3

- Index : 2

Index : 0 1 2 [3] 4 5

value : 5 7 3 [4] 9 1

4).

- Min : 3

- Index : 2

Index : 0 1 2 3 [4] 5

value : 5 7 3 4 [9] 1

5).

- Min : 1

- Index : 5

Index : 0 1 2 3 4 [5]

value : 5 7 3 4 9 [1]

값과 인덱스를 기억.

끝.

교환.

Index : [0] 1 2 3 4 [5]

value : [5] 7 3 4 9 [1]

첫 번째 값 : 5

끝의 값 : 1

두 개의 값의 자리를 교환한다.

교환완료.

Index : [0] 1 2 3 4 [5]

value : [1] 7 3 4 9 [5]

위의 과정을 모든 값들이 정렬될때 까지 반복한다.

Code

결과

변형된 버블정렬 (Bubble Sort)

앞서 했던 버블정렬은 리스트에 존재하는 값중 제일 큰 값을 찾아 리스트의 오른쪽 끝으로 밀어버리고,

그 다음 큰 값을 찾아 제일 오른쪽 자리를 제외한 오른쪽 끝으로 다음 큰 값을 밀어버리는 방법을 사용했다.

이번에 사용할 방법은 리스트에 존재하는 값중 제일 작은값을 첫 번째 자리에 확정하고,

그 다음 작은 값을 찾아 두 번째 자리에 확정, 그 다음 작은 값을 찾아 세 번째 자리에 확정하는 방식을 이용할 것이다.

※ 앞서했던 버블정렬과 변형된 버블정렬에 차이는?

결론만 말하자면 차이가 없다.

형태만 조금 다를뿐 기능과 연산량은 같다고 생각하면 된다.

구지 차이점을 말하자면 코드 길이가 조금 더 길다의 차이일 뿐이다.

▷ 정렬방법

1. 첫 번째 자리에 잡은 값을 중심으로 나머지 값들을 비교 한다.

2. 첫 번째에 자리한 값보다 비교하는 값이 작다면 자리를 바꾼다.

3. 이를 리스트의 끝까지 반복한다.

4. 첫 번째 비교 및 교환이 끝났다면 중심 값(자리)를 두 번째로 바꾼다.

5. 중심 값(자리)가 리스트의 끝 까지 갈때까지 이를 반복한다.

※ [ ]은 중심 값이다.

시작 : 5, 7, 3, 4, 9, 1

0.   [5], 7, 3, 4, 9, 1 - 5와 7을 비교 교환 X

1.   [5], 7, 3, 4, 9, 1 - 5와 3을 비교 교환 O

     [3], 7, 5, 4, 9, 1

2.   [3], 7, 5, 4, 9, 1 - 3과 4를 비교 교환 X

3.   [3], 7, 5, 4, 9, 1 - 3과 9를 비교 교환 X

4.   [3], 7, 5, 4, 9, 1 - 3과 1을 비교 교환 O

     [1], 7, 5, 4, 9, 3

5.   1, 7, 5, 4, 9, 3

다음은 2번째 자리의 값을 중심으로 그 뒤의 있는 값들을 위와 같은 방식으로 비교 및 교환 한다.

앞의 값들은 이미 정렬된 값이므로 비교하지 않아도 된다.

Code

결과

버블정렬(Bubble Sort)

 - 인접한 두 개의 값을 비교하여 크기가 순서대로 되어있지 않으면 두 개의 값의 자리를 교환하는 것.

 - 비교 및 판단 작업을 거처 가장 큰 값이 리스트 우측 끝으로 밀려나게 된다.

임의의 값을 정렬해보자.

정렬의 순서는 오름차순이다.

▷ 정렬방법.

1. 첫 번째 값과 두 번째 값을 비교한다.

2. 두 번째 값이 첫 번째 값 보다 더 크면 바꾸지 않는다.

3. 두 번째 값이 첫 번째 값 보다 더 작으면 바꾼다.

4. 두 번째 값과 세 번째 값을 비교한다.

5. 이를 n번째 값까지 반복한다.

6. 5번이 끝났으면 n번째에는 가장 큰 값이 존재하게 된다.

7. 모든 값이 정렬될때 까지 1~5번을 반복한다.

시작 : 5, 7, 3, 4, 9, 1

0.  5, 7, 3, 4, 9, 1

1.  5, 7, 3, 4, 9, 1

2.  5, 7, 3, 4, 9, 1

3   5, 3, 7, 4, 9, 1

4.  5, 3, 7, 4, 9, 1

5.  5, 3, 4, 7, 9, 1

6.  5, 3, 4, 7, 9, 1

7.  5, 3, 4, 7, 9, 1

8.  5, 3, 4, 7, 9, 1

9.  5, 3, 4, 7, 1, 9

한 번의 판단 및 교환이 끝나면 제일 큰 값이 우측으로 밀려나게된다.

이렇게 되었을 때 제일 우측에 있는값은 리스트에 존재하는 값들중에 제일 큰 값이므로

또 검사할 필요가 없어진다.

다음은 리스트에 존재하는 값들중 9를 제외한 가장 큰 값을 찾아서 6번째 자리를 제외한 5번째 자리로

밀어버린다.

이러한 과정들을 반복하면 정렬된 값들을 얻을 수 있게된다.

Code.

결과

정렬이란?

순서없이 나열된 자료를 특정한 키값에 따라 

오름차순이나 내림차순으로 재 배열하는 것을 의미한다.

정렬은 자료 탐색에 있어 필수적이다.

예를들어 사전에서 단어를 찾을 때 알파벳순으로 정렬되어 있지 않다면 특정한 단어를 찾는 것이 매우 힘들것이다.

물론 컴퓨터로 찾는다면 사람이 찾는것보다는 빨리 찾을 수 있을테지만, 탐색의 효율이 떨어지는것은 피할수 없다.

정렬은 많은 분류가 있지만 수행되는 공간에 따라 내부정렬과 외부정렬로 나뉘어 진다.

내부정렬은 정렬하고자 하는 모든 데이터가 메모리에 올라와 정렬이 수행되는 것을 의미한다.

외부정렬은 정렬하고자 하는 데이터가 너무 크기 때문에 모든 데이터를 메모리에 올려놓을 수 없으므로 일부만 올려놓은 상태에서 정렬한 이것을 다시 합하는 방식이다.

정렬의 종류

※ 내부정렬.

※외부정렬

균형적 다방향 머지 정렬.

정렬의 기본 동작

판단 : 두 값의 크기를 비교하여 크고 작음을 판단한다.

교환 : 판단 결과를 만족할 경우 두 값을 교환한다.