[C언어] 자료구조 -정렬(sorting) - 1, 선택정렬

정말 정말 고대하고 기대하고 기다렸던 매우 아주 심히 중요한

정렬을 배울 단계과 왔다. 사실 해싱에서 살짝 건드리기는 했지만

해싱은 조금 달라보여서 다르게 정리했고 여기서는 진짜 데이터를 정렬하는 시간을 가져보자.

 

 

정렬이란 어떠한 기준을 삼아서 오름차순 또는 내림차순으로 자료를 나열하는 것이다.

어떠한 기준이란 대부분(숫자)가 대신한다. 

 

 

 

 

여기서 다시 레코드랑 필드를 다시 정의해볼건데 복습이라고 생각하자 ㅎㅎ 어차피 데이터 배우면 항상 나옴

 

 

 

 

결국 저기 key 값이 기준이 되어서 정렬을 하는 거시다 ㅎㅎ

 

그런데 어떻게 정렬할 것이냐????????? 를 이제부터 알아볼 건데 

여러가지의 방법이 있다. 그니까 정렬마다 장단점이 있어서 그렇게 여러 방법을 고안해낸 것이다.

 

모든 경우에 대해 최적인 정렬 알고리즘은 없다. 그러면 알고리즘 하나겠지.. 아깝다 ㅠㅠ

그래서 해당 응용 분야에 적합한 정렬 방법 사용해야 하는 것이다.

 

고려사항

–레코드 수의 많고 적음 / 레코드 크기의 크고 작음

–Key의 특성(문자, 정수, 실수 등)

–메모리 내부/외부 정렬

 

•단순하지만 비효율적인 방법 : 삽입, 선택, 버블정렬 등

•복잡하지만 효율적인 방법: 퀵, 힙, 합병, 기수정렬 등

•정렬 알고리즘의 안정성(stability)

 

우선 제일먼저 알아볼 정렬이 선택정렬이다.

가장 생각하기 쉬운방법이다. 

 

정렬이 안된 숫자들 중에서 가장 작은 숫자를 선택해서 왼쪽(정렬된 위치)에 옮겨놓는 것이다.

즉 우측과 좌측이 구분되어서 좌측이 정렬된 배열, 우측이 정렬되지 않은 배열이다.

오른쪽에서 다 꺼낼 떄 까지 반복수행한다. 알고리즘으로 보면?

 

그림으로보면?

이런식이다.

 

왼쪽 리스트 (정렬된 리스트)	오른쪽 리스트 (정렬 안 된 리스트)	설명
( )	(5,3,8,1,2,7)	초기상태
(1)	(5,3,8,2,7)	1선택
(1,2)	(5,3,8,7)	2선택
(1,2,3)	(5,8,7)	3선택
(1,2,3,5)	(8,7)	5선택
(1,2,3,5,7)	(8)	7선택
(1,2,3,5,7,8)	()	8선택

눈에 잘보이네 굿굿굿

 

더 잘보이게 하자면

 

정말 코드도 간단하게 굿굿

 

 

아니면 다르게 짜자면

 

#include <stdio.h>

int main(void){
	int i, j, min, index, temp;
    int array[10] = {1,3,5,7,9,10,8,6,4,2};
    for(i = 0; i < 10, i++){
    	min = 99999; // 충분히 큰 숫자로 초기화
        for(j = i; j < 10; j++){ //정렬이 안된 부분으로부터의 최솟값 찾기
        	if(min > array[j]) { //for 문을 돌면서 최솟값찾기
            	min = array[j]; // 최솟값이라면 그 값을 저장
                index = j; // 최솟값을 가진 index 저장
            }
       	}
        temp = array[i]; // i번째에 있는 기존값을 뺌.
        array[i] = array[index]; // 최솟값을 가진 index의 값을 집어넣음
        array[index] = temp; // 기존의 값을 해당 index에 집어넣음
    }
    return 0;
}