'학교/자료구조'에 해당되는 글 6건

[정렬] 선택정렬과 삽입정렬

학교/자료구조 2016. 11. 5. 02:20

버블소트만큼 구현하기 쉽고 이해하기 쉬운 정렬들이다. 

하지만 이것도 버블소트와 마찬가지로 worst case에는 이기 때문에 

별로 효율적인 정렬과는 거리가 멀다.

 정렬하는 방식은 어떻게 짜느냐에 따라 방법이 다르고, 효율이 다르다.

 Insertion Sort와 Selection Sort는 삽입할때 정렬을 시켜서 삽입하느냐 아니냐에 따라

 방식이 달라진다. 삽입할 때 정렬을 시키는 방법은 아래와 같다.


 Selection Sort : 우선 어떤 배열(a)에서 앞에서부터 나아가며 

가장 작은 minimum값을 찾아 별도의 배열(b)의 제일 앞에 이동을 시킨다. 

그리고 a배열의 남은 값들중에서 다시 minimum값을 찾아 

b배열의 가장 뒤에 저장한다. 

이 과정을 n번 반복하면 a배열은 다 없어지고 b배열에 정렬된 형태로 남게된다.


 Insertion Sort : 키값을 앞에서부터 정해놓고 

키값이 바로 앞의 값보다 작을경우 두 수를 바꿔주면서 제일 앞에 있는 수까지 비교와 교환을 계속해주다가 

키값의 앞의 값이 키값보다 작을경우 즉, 정렬이 완료된 부분을 만날경우 

교환을 그만하고 다시 키값을 증가시켜서 과정을 반복한다.


두 과정다 worst case의 경우 가 나오지만 

Selection Sort는 무조건 끝까지 다 훑게되지만 

Insertion Sort는 중간에 정렬된 부분을 빨리 만난다면 끝까지 갈 필요가 없기때문에 

평균적으로는 Insertion Sort가 더 빨리 끝나게된다.



< 출처 : 유투브(YouTube) - Selection Sort >


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
#include <iostream>
#define MAXSIZE 5
using namespace std;
int main()
{
    int arr[] = { 2,4,3,5,1 };
    int min, num;
 
    cout << "정렬 전 : ";
    for (int i = 0;i < MAXSIZE;i++) {
        cout << arr[i] << " ";
    }cout << endl;
 
    for (int i = 0;i < MAXSIZE;i++) {
        min = arr[i];
        for (int j = i;j < MAXSIZE;j++) {
            if (min > arr[j]) {
                min = arr[j];
                num = j;
            }
        }
        swap(arr[i], arr[num]);
  
    }
 
    cout << "정렬 후 : ";
    for (int i = 0;i < MAXSIZE;i++) {
        cout << arr[i] << " ";
    }cout << endl;
 

    return 0;
}
cs

(c++)


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
package JaRyoGuJo;
 
public class InsertionSort {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int arr[] = {2,4,3,5,1};
        final int MAXSIZE = 5;
        int tmp;
        
        System.out.print("정렬 전 : ");
        for(int i =0;i<MAXSIZE;i++){
            System.out.print(arr[i]);
        }System.out.println("");
        
        for (int i = 0;i < MAXSIZE;i++) {
            for (int j = i;j > 0;j--) {
                if (arr[j-1] > arr[j]) {
                    tmp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = tmp;
                }
                else
                    break;
            }
        }
        
        System.out.print("정렬 후 : ");
        for(int i =0;i<MAXSIZE;i++){
            System.out.print(arr[i]);
        }System.out.println("");
        
    }
}
 
cs

(Java)




< 출처 : 유투브(YouTube) - Insertion Sort >


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
#include <iostream>
#define MAXSIZE 5
using namespace std;
 
int main()
{
    int arr[] = { 2,4,3,5,1 };
    int min;
 
    cout << "정렬 전 : ";
    for (int i = 0;i < MAXSIZE;i++) {
        cout << arr[i] << " ";
    }cout << endl;
 
    for (int i = 0;i < MAXSIZE;i++) {
        for (int j = i;j > 0;j--) {
            if (arr[j-1] > arr[j]) {
                swap(arr[j - 1], arr[j]);
            }
            else
                break;
 
        }
    }
 
    cout << "정렬 후 : ";
    for (int i = 0;i < MAXSIZE;i++) {
        cout << arr[i] << " ";
    }cout << endl;
 
    return 0;
}

cs

(c++)


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
41
package JaRyoGuJo;
 
public class SelectionSort {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int arr[] = { 2, 4, 3, 5, 1 };
        final int MAXSIZE = 5;
        int min, num = 0, tmp;
 
        System.out.print("정렬 전 : ");
        for (int i = 0; i < MAXSIZE; i++) {
            System.out.print(arr[i]);
        }
        System.out.println("");
 
        for (int i = 0; i < MAXSIZE; i++) {
            min = arr[i];
            for (int j = i; j < MAXSIZE; j++) {
                if (min > arr[j]) {
                    min = arr[j];
                    num = j;
                }
            }
            if (num != 0) {
                tmp = arr[i];
                arr[i] = arr[num];
                arr[num] = tmp;
            }
            num = 0;
        }
 
        System.out.print("정렬 후 : ");
        for (int i = 0; i < MAXSIZE; i++) {
            System.out.print(arr[i]);
        }
        System.out.println("");
 
    }
}
 
cs

(Java)

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

[정렬] 버블소트  (0) 2016.03.30
[정렬] sorting의 종류와 효율  (0) 2016.03.28
STL container -ing  (0) 2016.03.19
기초 Algorithm(2)  (0) 2015.11.03
기초 Algorithm(1)  (0) 2015.10.29
블로그 이미지

뭐해볼까

,

[정렬] 버블소트

학교/자료구조 2016. 3. 30. 01:43

 정렬중 가장 기본적인 정렬이고, 구현이 가장 쉽다는 장점이 있다. 하지만 시간이 비교적 오래걸린다는 단점을 가지고 있다.


 n번째 수와 n-1번째 수를 비교하여 큰수를 오른쪽으로 보낸다. 이 과정을 배열의 처음부터 끝까지 반복하면 제일 마지막에는 가장 큰 수가 올것이다. 이걸 n번 반복하면 결국은 모든 수가 오름차순으로 정렬이 된다.


9

3

1

7

5


3

9

1 

7

5


3

1

9

7

5


3

1

7

9

5


3

1

7

5

9

<Step 1>


 위 과정을 n번 반복하게되면 정렬된 배열이 나오게된다.

 버블소트의 worstcase는 입력되는 수가 역순으로 들어왔을 때 이고, averagecase역시 이며,  bestcase로는 이미 정렬이 되어있을 때의 O(1)이다. 

공간 복잡도는 배열의 크기인 O(1)이다.



3

1

7

5

9


1

3

7

5

9


1

3

7

5

9


1

3

5

7

9


1

3

5

7

9

<Step 2>


위 경우는 운좋게 두번만에 정렬이 되지만 코딩상 

이 과정을 <Step 5>까지 반복하게 된다.




< 출처 : 유투브(YouTube) - Bubble Sort >


(c++)


(java)

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

[정렬] 선택정렬과 삽입정렬  (1) 2016.11.05
[정렬] sorting의 종류와 효율  (0) 2016.03.28
STL container -ing  (0) 2016.03.19
기초 Algorithm(2)  (0) 2015.11.03
기초 Algorithm(1)  (0) 2015.10.29
블로그 이미지

뭐해볼까

,

[정렬] sorting의 종류와 효율

학교/자료구조 2016. 3. 28. 02:07

 입력되는 수들을 차례대로 정렬하기 위해서 쓰이는 알고리즘으로 사용자가 주로 사용할 함수에 따라 소팅과 구현방법을 정해서 사용하면 된다.

 흔히 쓰이는 정렬의 종류에는 bubble(거품), insertion(삽입), selection(선택), merge(병합), quick(퀵), heap(힙) 정렬들이 있고 이 외에도 shell, radix, BinarySerchTree, AVLtree 등이 있다.



Sort

bubble

insertion

selection

heap

merge

quick

shell

Average

 


Worst

 


구현이 가장 쉬움

. 

 

  

 별도의 메모리 필요(링크드리스트로 해결)

같은 의 속도를 갖는 정렬중 가장 빠름

 

*Big-Oh Complexity(빅-오 복잡도) : O(1) < < O(n) <  < < 




< 출처 : 유투브(YouTube) - 15 Sorting Algorithms in 15 Minutes >



< 출처 : 유투브(YouTube) - Visualization and Comparison of Sorting Algorithms >

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

[정렬] 선택정렬과 삽입정렬  (1) 2016.11.05
[정렬] 버블소트  (0) 2016.03.30
STL container -ing  (0) 2016.03.19
기초 Algorithm(2)  (0) 2015.11.03
기초 Algorithm(1)  (0) 2015.10.29
블로그 이미지

뭐해볼까

,

STL container -ing

학교/자료구조 2016. 3. 19. 03:19

STL이란 : Standard Template Library의 약자로 일반적으로 많이 사용이 되는 자료구조와 알고리즘을 일반화해서 사용하기 쉽도록 만들어놓은 라이브러리이다.


장점 : 처음부터 일일이 짤 필요가 없고 #include로 선언을 하고 사용하면 되기때문에 소스의  크기가 줄어든다.

단점 : 처음 배울때 시간을 많이 투자해야한다.

가독성이 떨어진다.


STL의 종류 : vector, list, stack, queue, map, set, deque, multiset, multimap, priority_queue


이것들도 각자의 성향에 따라 분류가 되는데 우선, 순차적컨테이너는 삽입과 삭제를 할때 순차적으로 이뤄지는 컨테이너다. 연관컨테이너는 삽입할 때마다 기본적으로 정렬이 되어서 들어가게된다. 그리고 이진트리구조를 갖는다. 마지막으로 어댑터컨테이너는 stack은 LIFO(Last In First Out), queue는 FIFO(First In Frist Out)처럼 정해진 방법으로 삽입삭제가 이루어진다.


순차 컨테이너(Sequence Container) : vector, list, deque

연관 컨테이너(Associate Container) : map, set, multimap, multiset

어댑터 컨테이너(Adapter Container) : stack, queue, priority_queue


 컨테이너

 설명

Vector 

 뒤에 삽입이나 삭제시 속도가 빠르지만 중간에 할경우는 해당 위치에따라 속도가 다르다.

 인덱스값으로 접근이 가능하기때문에 검색속도가 빠르다

List 

 위치에 상관없이 삽입과 삭제가 빠르게 이뤄질수 있다.

 순차적으로 검색을 해야하고, 벡터처럼 임의의 접근을 할수 없다.

Deque

 앞뒤로 삽입과 삭제가 빠르고, 중간에 할경우에는 해당 위치에 따라 속도가 다르다.

 인덱스값으로 접근이 가능하기때문에 검색속도가 빠르다.



 컨테이너 

 설명 

Map 

 키와 데이터를 같이 관리하는데, 키는 중복이 허용되지 않는다.

 키값을 이용하여 원하는 데이터를 찾을 수 있다.

 삽입과 삭제가 빠르지만 삽입할때마다 정렬을 한다.

 양방향 반복자를 사용한다.

Set 

 map과 비슷하지만 키만 갖고, 중복이 허용되지 않는다.

 검색, 삽입, 삭제가 빠르다.

 양방향 반복자를 사용한다.

Multimap 

 map과 다른요인은 동일하지만, 키값이 중복될 수 있다.

Multiset

 set과 다른요인은 동일하지만, 중복이 가능하다.




 컨테이너 

 설명 

Stack 

 top에서만 삽입과 삭제가 이루어진다.

Queue 

 삽입은 뒤에서 삭제는 앞에서 이루어진다.

Priority_queue 

 큰 값부터 차례대로 정렬이 이루어진다.

 가장 큰 값의 접근과 삭제가 빠르게 이루어진다.


삽입과 삭제가

 중간에서 많이 일어날 경우 : list

 앞에서 많이 일어날 경우 : deque, list

 뒤에서 많이 일어날 경우 : stack, queue


임의의 접근이 일어날 경우 : vector, deque


가장 큰 값을 많이 찾는 경우 : priority_queue



 

vector

list 

deque

map

set

stack

queue

priority_queue

삽입

O(n)

O(1)

O(1)

O(log n)

O(log n)

O(1)

O(1)

O(1) / O(n)

삭제

O(n)

O(1)

O(1)

O(log n)

O(log n)

O(1)

O(1)

O(n) / O(1)

검색

O(1)

O(n)

O(log n)

O(log n)

O(log n)

 

 

 


 

 

 

 

 

 top에서만

 

 



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

[정렬] 선택정렬과 삽입정렬  (1) 2016.11.05
[정렬] 버블소트  (0) 2016.03.30
[정렬] sorting의 종류와 효율  (0) 2016.03.28
기초 Algorithm(2)  (0) 2015.11.03
기초 Algorithm(1)  (0) 2015.10.29
블로그 이미지

뭐해볼까

,

기초 Algorithm(2)

학교/자료구조 2015. 11. 3. 01:41

Stack push{

if size() = N then

throw StackFull exception

t<-t + 1

S[t]<-e

}

Stack pop{

if empty() then

throw StackEmpty exception

t<-t-1

}

enqueue{

if size() = N then

throw QueueFull exception

Q[r] <- 2

r <- (r+1) mod N

n = n+1

}

dequeue{

if empty() then

throw QueueEmpty exception

f <- (f+1) mod N

n = n-1

}

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

[정렬] 선택정렬과 삽입정렬  (1) 2016.11.05
[정렬] 버블소트  (0) 2016.03.30
[정렬] sorting의 종류와 효율  (0) 2016.03.28
STL container -ing  (0) 2016.03.19
기초 Algorithm(1)  (0) 2015.10.29
블로그 이미지

뭐해볼까

,

기초 Algorithm(1)

학교/자료구조 2015. 10. 29. 22:38

singleNode 구현

{

public:

string elem;

SNode next;

}

singleNode 삽입

{

SNode* v = new SNode;

v->elem = e;

v->next = head;

head = v;

}

singleNode 제거

{

SNode* old = head;

head = old->next;

delete old;

}

singleNode add back

{

SNode* v = new SNode;

v->elem = e;

v->next = NULL;

tail->next = v;

tail = v;

}

doubleNode 구현

{

public:

string elem;

DNode* next;

DNode* prev;

}

doubleNode 삽입(v 앞에)

{

DNode* u = new DNode;

u->elem = e;

u->next = v;

u->prev = v->prev;

v->prev->next = v->prev = u;

}

doubleNode 삭제

{

DNode* u = v->prev;

DNode* w = v->next;

u->next = w;

w->prev = u;

delete v;

}

CircleNode 삽입

{

CNode* v= new CNode;

v->elem = e;

if(cursor == NULL){

v->next = v;

cursor = v;

}else{

v->next = cursor->next;

cursor->next = v;

}

}

CircleNode 삭제

{

CNode* old = cursor->next;

if(old == cursor)

cursor = NULL;

else

cursor->next = old->next;

delete old;

}



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

[정렬] 선택정렬과 삽입정렬  (1) 2016.11.05
[정렬] 버블소트  (0) 2016.03.30
[정렬] sorting의 종류와 효율  (0) 2016.03.28
STL container -ing  (0) 2016.03.19
기초 Algorithm(2)  (0) 2015.11.03
블로그 이미지

뭐해볼까

,

공지사항

글 보관함

달력

«   2025/07   »
일 월 화 수 목 금 토
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

티스토리툴바