Selection Sort with C

-
수업 중 selection sort를 C로 구현하는 게 있어 업로드 합니다? 한다?
매번 C++ 을 쓰다가 C를 쓰니 문법이 기억날랑말랑 했다.
하지만 멀록은 내가 가장 좋아하는 명령어라서 기억이 났다.



Selection sort 과정
Selection sort은 정렬 기법 중에 하나로 구현은 쉽지만 시간복잡도가 크다.
오래 걸린다는 뜻이다. Selection sort의 구현방법은 다음과 같다.

(오름차순 기준)
1. N개의 숫자가 무작위로 있다고 가정할 때, 각각 1번, 2번 ... N-1번, N번 이라고 생각해보자.
2. index를 1로 초기화한다
3. index번 ~ N번까지 중 가장 작은 수를 찾는다.
4. 젤 작은 것을 찾아 index 위치의 수와 자리를 바꾼다.
5. index++을 해준 뒤 2,3 번을 index가 N이 될 때까지 해준다.

대강 { 1, 5, 3, 6, 4, 2, 7, 9, 8, 6 } 이 있다고 가정하면
결과는 { 1, 2, 3, 4, 5, 6, 7, 8, 9 } 가 되는 것이다.(정렬이니 당연하다)



시간복잡도 정리
첫 번째 자리의 수를 찾기위해 N번의 탐색,
두 번째 자리의 수를 찾기위해 N-1번의 탐색,
세 번째 자리의 수를 찾기위해 N-2번의 탐색
...
...
...
N-1 번째 자리의 수를 찾기위해 2번의 탐색,
N 번째 자리의 수를 찾기위해 1번의 탐색.

탐색한 수를 전부 더하면 N(1+N) / 2 이다.
합공식이 가물가물한데.. 사실 시간복잡도 계산에선 차수가 제일 큰 놈이 중요하기 때문에
째깐둥이들은 조금 엇나가도 괜찮을 거다.

N(1+N) / 2 = 1/2(N^2 + N)
여기서 차수가 제일 큰 놈은 N^2이니, 앞뒤로 다 떼어주면 
시간복잡도는 O(N^2)가 되는 것이다.



소스코드 정리

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdio.h>
 
void swap(int arr[], int x, int y);
void selectionSort(int arr[], int size);
 
int main(void)
{
    int N;
    scanf("%d", &N);
 
    int *arr = (int*)malloc(sizeof(int) * N);
    for(int i = 0; i < N; i++)
    {
        scanf("%d", &arr[i]);
    }
 
    selectionSort(arr, N);
 
    for(int i = 0; i < N; i++)
    {
        printf("%d ", arr[i]);
    }
    free(arr);
    system("pause");
    return 0;
}
 
 
void swap(int arr[], int x, int y)
{
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}
 
void selectionSort(int arr[], int size)
{
    for(int i = 0; i < size -1 ; i++)
    {
        int min = arr[i];
        int index = i;
        for(int j = i; j < size; j++)
        {
            if(min > arr[j])
            {
                min = arr[j];
                index = j;
            }
        }
 
        if(index != i)
        {
            swap(arr, index, i);
        }
    }
}
cs






N을 입력받고, N개의 무작위 정수를 입력받는다.
이후 정렬된 N개의 수를 출력한다.

위의 'Selection sort 과정'을 읽으면 이해에 도움이 될 것이다.

댓글

댓글 쓰기

이 블로그의 인기 게시물

C++ int, long int, long long int 어떤 걸 써야할까

-
이미지
(출처:  https://ko.cppreference.com/w/cpp/language/types ) (LP32, ILP32, LLP64, LP64는 data model을 나타내며, 글 맨 아래 '참고'에 정리해둠) C++ 정수형 데이터 타 입들 C++ standard를 기준으로      short                     - 최소 16비트      int                         - 최소 16비트      long int                - 최소 32비트      long long int        - 최소 64비트 (C++ standard는 정수형 데이터 타입의 명확한 크기를 정해두지 않았다.  다만 최소한의 하한선만 정해놓았다) 일반적으로 short 는 16 비트 , int 는 32 비트로 알고 있다 . 그래서 int 는 -2^31 ~ 2^31 – 1 범위의 정수를 표현할 수 있고 , 이보다 크거나 작은 정수를 표현하기 위해서는 비트수가 더 필요하다 . 그러면 long 을 써야하나 long long 을 써야하나 ? 확실한 방법은 long long int 를 쓰는 것이다 . C++ 표준을 보면 long int 는 최소 32 비트를 보장한다고 한다 . -2^31 ~ 2^31 – 1 범위를 넘어서는 정수를 표현하기 위해서는 C++ 표준 기준으로 최소 64 비트를 보장하는 long long int 를 써야한다 . (long int를 쓸 경우, 윈도우 환경에서는 int와 똑같은 범위까지만 표현할 수 있다) // 나만의 생각 시작 그러면 long int 는 필요 없는 것 아닌가 ? ILP32, LLP64, LP64 data model만 고려한다면 그렇다고 볼 수 있지 않을까 싶다. 왜냐하면 위 세 개의 data model 에서는 int 와 long int 의 비트수가 같거나,  long int 와 long long int 의 비트수가 같기 때문이다 . long int가 int
자세한 내용 보기

C++ fstream 간단한 사용법(파일입출력)

-
이미지
인터넷을 돌아다니다 보니, 파일입출력은 기본 중에 기본이라고 한다. C++를 주로 사용하고 있지만 파일입출력을 할 줄 몰랐다. 그래서 정리한다. (내용출처 :  http://www.cplusplus.com/doc/tutorial/files/  ) <fstream>  C++는 <fstream> 이라는 Stream class를 지원한다. '파일에서 읽어오거나 파일에 쓰는 클래스' 라고 한다. istream과 ostream의 파생클래스이다(자식임).  <fstream>에서 주로 쓰는 두 가지는 ofstream 과 ifstream 이다. ofstream  ofstream은 'output file stream'이다. output이라길래 파일의 내용을 읽어오는 줄 알았는데 내 생각과 반대로 파일에 적는 친구다. ofstream에는 멤버함수 open이 있다. 사용법은 평소에 쓰던 cin, cout 과 비슷하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include   < iostream > #include   < fstream > using   namespace   std ; int  main( void ) {      // 파일 열기     ofstream myfile;     myfile.open( "example.txt" );           // 파일에 쓰기     myfile  < <   "Wow.\n" ;     myfile  < <   "Writing this to a file.\n" ;           // 파일 닫기     myfile.close();    
자세한 내용 보기

x86 OS interrupts routine

-
x86 운영체제에서는 다음과 같은 과정을 거쳐 interrupt 를 호출한다 1.       interrupt n instruction 수행 . 2.       IDT 에 등록되어있는 ISR(interrupt Service Routine) 수행 . xv6 는 위의 두 과정을 아래와 같이 진행한다 . 1. interrupt n instruction - “int n” instruction workflow. 1)        IDT(interrupt descriptor table) 에서 n’th descriptor 를 읽어온다 . -  시스템 부팅시 tvinit() 함수로 vertors.S 의 번호 , DPL 을 다 초기화 해줌 . -  system call은 DPL이 유저 레벨로 세팅됨 2)        CPL 이 DPL 보다 작거나 같은지를 확인함 ( 커널 모드 : 0, 유저 모드 : 3, 부를 수 있는지 없는지를 확인하는 것 ) -   이 조건을 충족하지 못하면 부를 수 없는 interrupt 를 부른 것이라 exception 이 발생한다 . 3)        만약 target segment selector 의 PL 이 CPL 보다 작으면 PL 의 변환이 필요하다 (ex PL 이 커널모드인 경우 ). 다음 3 단계를 거쳐서 변환이 일어남 . (1)   현재 유저모드니깐 , 유저모드의 esp, ss register 를 임시로 저장함 ( 임시로 저장하는 이유는 커널 스택에다 푸시하기 위해서 ) (2)   task segment descriptor 에서 esp, ss 를 불러와서 CPU-internal registers 에 저장함 . (3)   이제 아까 임시로 저장한 esp, ss 를 푸시해줌 ( 유저 모드로 돌아가기 위한 esp, ss) 4)        eflags, cs, eip register 를 stack 에 푸시한다 . -   당연히 여기는 Kernal Stack 임 .
자세한 내용 보기