정렬(sort)은 주어진 데이터를 일정한 규칙에 따라 다시 나열하는 것으로, 데이터를 정렬할 때 오름차순이나 내림차순으로 정렬

• 오름차순은 데이터를 작은 순에서 큰 순으로 나열

• 알파벳은 A에서 Z로, 한글은 ㄱ에서 ㅎ순으로 정렬

• 내림차순은 오름차순의 반대로 나열하는 방법

• 1번째와 2번째 원소를 비교하여 정렬, 2번째와 3번째, ..., n-1번째와 n번째를 정렬한 뒤 다시 처음으로 돌아가 비교하며 정렬

버블 정렬

• 인접한 2개씩 비교

int Bubble( int arg[], int n ) {
	int last, i;
	int temp, count=0;
	int flag = 0;	// 깃발..표시..
	
	for( last = n; last > 1; last-- ) {		// last++ 
		flag = 0;
		for( i = 0; i < last - 1; i++ ) {	// i--
			if( arg[i] > arg[i+1] ) {
				temp = arg[i];
				arg[i] = arg[i+1];
				arg[i+1] = temp;
				flag = 1;
				count++;
			}
		}
		
		if( flag == 0 ) {
			Display( Data, n ); // 과정을 보여주기..
			printf(" Count %d \\n", count );
			return 0;
		}
		Display( Data, n ); // 과정을 보여주기.. 
	}
	
	printf(" Count %d \\n", count );
	return 0;
}

• 특성
  • 안정적 알고리즘 : 정렬 전에 동일한 키를 갖는 쌍의 상대적인 위치가 정렬 후에도 그대로 유지
  • 제자리 알고리즘 : 입력 공간 이외의 별도의 메모리를 사용하지 않음
  • 주어진 키가 모두 역순으로 정렬되어 있는 경우 최악의 실행시간
  • 최악의 경우 : O(n^2)

삽입 정렬

• 미정렬 부분의 첫 번째 원소로부터 정렬된 부분의 제자리에 삽입하는 방법

• 특성
  • 미정렬된 부분의 첫 번째 원소를 정렬된 부분의 적당한 위치로 교환하면 됨
  • 안정적 알고리즘
  • 제자리 알고리즘
  • 최악의 경우 : O(n^2)

선택 정렬

• 정렬되지 않은 데이터 중에서 가장 작은 것을 선택한 후, 선택된 데이터를 미정렬 데이터의 첫 번째 원소와 교환하는 과정을 반복하는 정렬 방법