배열, 버블 정렬

Yama·2023년 12월 7일

어소트락 수업

목록 보기

9/55

배열(Array)

	int i0 = 0;
	int i1 = 0;
	int i2 = 0;
	int i3 = 0;
	int i4 = 0;
	// int i0 = 0, i1 = 0; i2 = 0; i3 = 0; i4 = 0; 같은 의미

다른 이름의 int변수 5개를 배열없이 선언해줄려면 이렇게 해줘야한다.(비효율)

int Arr[5] = {};

자료형 배열이름[개수];
int 5개짜리를 한번에 선언한것.
{}는 5개짜리를 싹다 0으로 초기화

배열의 초기값

int Arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8 , 9, 10 };

초기값 정해주기.
인덱스에 순서대로 들어간다

int Arr[10] = { 1, 2, 3, 4, 5, }; //{ 1, 2, 3, 4, 5 };

5 다음거부터는 0으로 초기화된다.

int Arr[10] = { }; // { 0 };

int 10개 선언, 전체를 0으로 초기화

[]

인덱스라고한다.

Arr[4] = 10;

5번쨰 칸에 10을 넣겠다.
- 왜? 5번째칸? 인덱스는 0부터 시작해서

배열의 메모리 구조는 연속적인 구조.

int Arr[10] = {};

메모리에 연속으로 4바이트 짜리 10개를 연속으로 잡는다.

배열의 이름은 해당 배열의 시작위치(주소)

O표기법의 속도

O(1) - > O(logN) -> O(N) -> O(N * logN)(이걸 가장 많이 사용) -> O(N^2)

O(N^2) 종류

버블 정렬
삽입 정렬

O(N * logN)

퀵소트(쾌속정렬)(불안정 정렬)
머지소트(합병정렬)(안정정렬)
힙소트

안정 정렬과 불안정 정렬

정렬의 기준이 여러개인 경우, 이전 정렬 순서가 남아있는지 아닌지 여부
ex)
- 정치가 1순위 지능을 2순위로 정렬을하고싶다.
- 지능 스택을 먼저 정렬하면 상위권 3개 66,55,44순으로 높은차순으로 정렬시킨다
- 정치를 스탯을 정렬햇는데 100,100,100했다.
- 이떄 지능스탯이 높은순으로 정렬되어있다면 안정정렬, 이상하게되있다면 불안정 정렬

버블 정렬

서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 이다.
ex)
- 10,1,9,7,을 오름 차순으로 정렬하고 싶다면
  - 첫번쨰 비교 10,1 비교 10이 더크기 때문에 1,10,9,7
  - 두번쨰 10,9 비교 -> 1,9,10,7
  - 세번쨰 10,7 비교 -> 1,9,7,10
  - 4번째부터는 맨 오른쪽에 10을 제외하고 정렬.
  - 4번쨰 1,9 비교 -> 1,9,7
  - 5번쨰 9,7 비교 -> 1,7,9
  - 6번째부터는 9 제외하고 정렬.
  - 6번째 1,7 비교 -> 1,7
단점
- (n-1) + (n-2) + (n-3) +... 1
- O표기법은 최고차항의 지수만 놔두고 다 버린다.

버블 정렬 예시 코드.

	int iArray[10] = { 44, 99, 47, 76, 26, 11 ,46, 87, 56, 28 };

	int iNum = sizeof(iArray) / sizeof(int); // sizeof는 자료형의 크기를 알려줌. 40 / 4

	for (int j = 0; j < iNum - 1; ++j) // 이중 for문
	{
		for (int i = 0; i < iNum - (1 + j); ++i)
		{
			if (iArray[i] > iArray[i + 1])
			{
				int Temp = iArray[i];
				iArray[i] = iArray[i + 1];
				iArray[i + 1] = Temp;
			}
		}
	}

순서
- iArray 배열에 10개의 순서대로 10개의 순서를 대입한다
- iNum에 값은 4x개수 / 4
- j값이 0일떄
  - i가 0일떄 비교를한다싹다 끝나고
  - i가 1일떄
  - ...
  - i가 8일떄까지 반복
- j값이 1일떄
  - i가 0일떄 비교를한다싹다 끝나고
  - i가 1일떄
  - ...
  - i가 7일떄까지 반복
- j값이 2~7
- j값이 8일떄
  - i가 0일떄 비교하고 끝.
- 그리고 for문 탈출.

버블 정렬 최적화

	for (int j = 0; j < iNum - 1; ++j)
	{
		bool bSwap = false;

		for (int i = 0; i < iNum - (1 + j); ++i)
		{
			if (iArray[i] > iArray[i + 1])
			{
				// 데이터 스왚
				int Temp = iArray[i];
				iArray[i] = iArray[i + 1];
				iArray[i + 1] = Temp;

				bSwap = true;
			}

			// 1 break; 하면  for (int i = 0; i < iNum - (1 + j); ++i)탈출
		}

		if (!bSwap) // 탈출구문.
		{
			break; // 큰 for문 탈출구문.
		}

강의 코드

#include <iostream>


int main()
{
	// 배열(Array)
	int i0 = 0, i1 = 0, i2 = 0, i3 = 0, i4 = 0;

	int Arr[10] = {};

	Arr[0] = 10;
	Arr[1] = 10;
	Arr[2] = 20;


	int iArray[10] = { 44, 99, 47, 76, 26, 11, 46, 87, 56, 28 };

	int iNum = sizeof(iArray) / sizeof(int);


	for (int j = 0; j < iNum - 1; ++j)
	{
		for (int i = 0; i < iNum - (1 + j); ++i)
		{
			if (iArray[i] > iArray[i + 1])
			{
				int Temp = iArray[i];
				iArray[i] = iArray[i + 1];
				iArray[i + 1] = Temp;
			}
		}
	}

	return 0;
}