참된코딩 :: 참된코딩

빅오

자료구조 2017. 1. 1. 21:00

알고리즘	최선	평균	최악
삽입 정렬	O(n)	O(n²)	O(n²)
선택 정렬	O(n²)	O(n²)	O(n²)
버블 정렬	O(n²)	O(n²)	O(n²)
쉘 정렬	O(n)	O(n^1.5)	O(n^1.5)
퀵 정렬	O(n log n)	O(n log n)	O(n²)
히프 정렬	O(n log n)	O(n log n)	O(n log n)
합병 정렬	O(n log n)	O(n log n)	O(n log n)
기수 정렬	O(dn)	O(dn)	O(dn)

저작자표시 비영리 변경금지

'자료구조' 카테고리의 다른 글

쉘 정렬 (Shell sort) (0)	2017.01.02
삽입정렬 (Insertion sort) (0)	2017.01.01
선택정렬 (Selection sort) (0)	2017.01.01
변형된 버블정렬 (Bubble Sort) (0)	2017.01.01
버블정렬(Bubble Sort) (0)	2017.01.01

Posted by 비선형구조

선택정렬 (Selection sort)

자료구조 2017. 1. 1. 20:13

▷ 선택정렬(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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;
 
#define MAX            6
 
void SelectSort(int *Number );
void main()
{
    int Number[MAX] = {5,7,3,4,9,1};
 
    SelectSort( Number );
 
    for(int i = 0; i < MAX; i++)
        printf("%d \n", Number[i] );
}
 
void SelectSort( int *Number )
{
    int Min;
    int Index;
 
    for(int i = 0; i < MAX; i++)
    {
        Min = Number[i];
        Index = i;
 
        for(int j = i + 1; j < MAX; j++)
        {
            if(Min > Number[j])
            {
                Min = Number[j];
                Index = j;
            }
        }
 
        int Temp = Number[Index];
        Number[Index] = Number[i];
        Number[i] = Temp;
    }
}
Colored by Color Scripter
cs

결과

저작자표시 비영리 변경금지

'자료구조' 카테고리의 다른 글

삽입정렬 (Insertion sort) (0)	2017.01.01
빅오 (0)	2017.01.01
변형된 버블정렬 (Bubble Sort) (0)	2017.01.01
버블정렬(Bubble Sort) (0)	2017.01.01
정렬이란? (0)	2017.01.01

Posted by 비선형구조

변형된 버블정렬 (Bubble Sort)

자료구조 2017. 1. 1. 18:40

변형된 버블정렬 (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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
 
#define MAX            6
 
void BubleSort(int *Number );
void main()
{
    int Number[MAX] = {5,7,3,4,9,1};
 
    BubleSort( Number );
 
    for(int i = 0; i < MAX; i++)
        printf("%d \n", Number[i] );
}
 
void BubleSort(int *Number)
{
    for(int i = 0; i < MAX; i++)
    {
        for(int j = i + 1; j < MAX; j++)
        {
            if(Number[i] > Number[j])
            {
                int Temp = Number[i];
                Number[i] = Number[j];
                Number[j] = Temp;
            }
        }
    }
}
Colored by Color Scripter
cs

결과

저작자표시 비영리 변경금지

'자료구조' 카테고리의 다른 글

삽입정렬 (Insertion sort) (0)	2017.01.01
빅오 (0)	2017.01.01
선택정렬 (Selection sort) (0)	2017.01.01
버블정렬(Bubble Sort) (0)	2017.01.01
정렬이란? (0)	2017.01.01