C와 JAVA로 선택 정렬(selection sort) 구현하기

1. 주어진 리스트 중에 최소값을 찾음
2. 그 값을 맨 앞에 위치한 값과 교체함 (제일 작은 값이 맨 앞에 위치하게 됨)
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체함
4. 하나의 원소만 남을 때까지 1 ~ 3을 반복함

 

쉽게 말하자면 리스트의 모든 값들을 비교해서 가장 작은 값을 찾아 리스트의 맨 첫번째에 놓고 (첫번째 과정)

두번째로 작은 값을 찾아 리스트의 두번째 자리에 놓는다(두번째 과정)

 

이런식으로 리스트의 길이만큼 과정을 거친다.

 

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 정렬하는 데에는 최대 (n * n) 만큼의 시간이 걸린다. 리스트의 전부를 비교하니 당연하다.

 

 

 

C로 짠 코드

#include <stdio.h>


int main(int argc, char *argv[]){
    int list[] = {8, 6, 7, 3, 5};

    int indexMin, temp;

    printf("정렬 전의 리스트 : ");

    for (int i = 0; i < sizeof(list) / sizeof(int); i++) {
        printf("%d ", list[i]);
    }
    printf("\n");


    for (int i = 0; i < sizeof(list) / sizeof(int); i++){
        indexMin = 1;
        for (int j = i + 1; j < sizeof(list) / sizeof(int); j++){
            if (list[j] < list[indexMin]){
                indexMin = j;
            }

        }

        temp = list[indexMin];
        list[indexMin] = list[i];
        list[i] = temp;

        printf("패스 %d 후의 리스트 ", i + 1);

        for (int k = 0; k < sizeof(list) / sizeof(int); k++) {
            printf("%d ", list[k]);
        }
        printf("\n");
        
    }
}

 

 

 

자바로 짠 코드

package com.company;

public class Main {

    public static void main(String[] args) {
	    int list[] = {8, 6, 7, 3, 5};

        int indexMin, temp;

        System.out.print("정렬 전의 리스트 ");
        for (int m:list){
            System.out.print(m + "");
        }
        System.out.println();

        for (int i=0; i < list.length - 1; i++){
            indexMin = 1;
            for (int j = i + 1; j < list.length; j++){
                if (list[j] < list[indexMin]){
                    indexMin = j;
                }
            }

            temp = list[indexMin];
            list[indexMin] = list[i];
            list[i] = temp;

            System.out.print("패스 " + (i + 1) + "후의 리스트 ");
            for (int n:list){
                System.out.print(n + "");
            }
            System.out.println();
        }
    }
}

 

결과

 

 

코드는 다 비슷비슷 하다. 문법의 차이만 조금 있을 뿐.