대바보의 끄적끄적

순서를 맞춰주는것을 정렬이라한다.
논리적으로 생각해보고 펜으로도 써보자.

기본적인 선택정렬을 알아보자.
목표 : 배열에서 가장 큰수와 작은수의 자리를 바꾼다.

#include <iostream>

using namespace std;

int main()
{
	const int length = 5;

	int aArr[length] = { 3,5,2,1,4 };
	/*
	정렬순서
	3,5,2,1,4
	1,5,2,3,4
	1,2,5,3,4
	1,2,3,5,4
	1,2,3,4,5
	*/
	for (int i = 0; i < length-1; i++) {
		int temp = 0;
		int arr = i;
		for (int s = 0; s < length - i; s++) {
			cout << aArr[arr] << " > " << aArr[s + i] << endl;
			if (aArr[arr] > aArr[s + i]) {
				arr = s + i;
				
			}
		}
		{
			temp = aArr[arr];
			aArr[arr] = aArr[i];
			aArr[i] = temp;
		}
	}

	cout << "sort" << endl;
	for (int i = 0; i < length; i++) {
		cout << aArr[i] << endl;
	}

	return 0;
}

기본적인 버블정렬을 알아보자.
목표 : 배열의 데이터를 순차적으로 비교하여 
앞데이터가 다음배열보다 클경우 자리를 바꾼다.

#include <iostream>

using namespace std;

int main() {

	int len = 5;
	int a[] = { 5,2,3,4,1 };

	for (int i = 0; i < len-1; i++) {
		for (int s = 0; s < len - (i+1); s++) {
			//cout << "s : " << s << " a[s+1] : " << a[s + 1] << endl;
			if (a[s] > a[s + 1]) {
				int temp = a[s + 1];
				a[s + 1] = a[s];
				a[s] = temp;
			}//end of if
		}//end of for s
	}//end of for i
	for (int i = 0; i < len; i++) {
		cout << a[i] << endl;
	}
	return 0;
}

위 로직이 실행되게되면 10자리의 배열에 0~9까지 값이 랜덤으로 생성된다.

생성된 숫자 : 1338675973

위 로직을 일부 해석해보겠다.

빨간색으로 표시된 부분이 비교하는 부분이다.

배열[0]의 값 1과 3을 비교한다.

1338675973

배열[1]의 값 3과 3을 비교한다.

1338675973

배열[2]의 값 3과 8을 비교한다.

1338675973

배열[3]의 값 8과 6을 비교한다.

1338675973

배열[3]의 데이터가 배열[4]의 데이터보다 크다

배열[3] : 8과 배열[4] : 6 위치를 변경 -> 13368(위치변경)75973

배열[4]의 값 8과 7을 비교한다.

1336875973

배열[4]의 데이터가 배열[5]의 데이터보다 크다

배열[4] : 8와 배열[5] : 7 위치를 변경 -> 133678(위치변경)5973

배열[5]의 값 8과 5을 비교한다.

1336785973

배열[5] 데이터가 배열[6]의 데이터보다 크다

배열[5] 데이터 : 8와 배열[6] 데이터 : 5 위치를 변경 -> 1336758(위치변경)973

배열[6]의 값 8과 9를 비교한다.

1336758973

배열[7]의 값 9과 7를 비교한다.

1336758973

배열[7] 데이터가 배열[8]의 데이터보다 크다

배열[7] 데이터 : 9과 배열[8] 데이터 : 7 위치를 변경 -> 133675879(위치변경)3

배열[8]의 값 9과 3를 비교한다.

1336758793

배열[8] 데이터가 배열[9]의 데이터보다 크다

배열[8] 데이터 : 9와 배열[9] 데이터 : 3 위치를 변경 -> 1336758739(위치변경)

이런식으로 반복되면 맨 뒷자리는 가장 큰수가 남게된다.

맨 뒷자리 값을 가장 큰수이므로 비교 하지않고 하나씩 작은 숫자로 반복하게된다.

또 check값으로 데이터의 변경이 없을 경우 즉 정렬 완료시 반복을 중지한다.