[강의] 11월 19일 수업정리

오늘은 선택 정렬과 삽입정렬에 대한 수업을 들었다.

 

1. 암기 

1. 단일 원소 배열은 이미 정렬된 배열이다.
   • 원소가 하나뿐인 배열은 비교 대상이 없으므로 항상 정렬된 상태로 간주한다.
2. 선택 정렬, 삽입 정렬 등과 같은 정렬 알고리즘은 원칙에 따라 구현한다.
   • 알고리즘에 명시된 단계들을 그대로 따라 작성해야 한다.
   • 불필요하게 복잡하게 만들지 말고, 기본 원칙을 준수하며 구현한다.
3. 코드를 볼 때는 핵심 로직을 파악한다.
   • 알고리즘의 중요한 흐름(핵심 로직)을 먼저 이해하고, 이를 중심으로 코드의 구조를 해석하거나 작성한다.

 

2. 선택 정렬

2.1 핵심 로직 

• 첫 번째 자료를 두 전째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위쳉 놓는 과정을 반복하는 것 

#include <iostream>

int findMinDataIndex(const int* pData, int nLength);
void printData(const int* pData, int nLength);
void swapData(int& nDst, int& nSrc);
void selectionSortLogic(int* pData, int nLength);
void selectionSort(int* pData, int nLength);

int main()
{
	int arData[9]{5,7,4,1,9,2,3,6,8};

	selectionSort(arData, 9);
	printData(arData, 9);

}

void selectionSortLogic(int* pData, int nLength)
{
	swapData(pData[0], pData[findMinDataIndex(pData, nLength)]);

}

void selectionSort(int* pData, int nLength)
{
	while (nLength > 1)
	{
		selectionSortLogic(pData, nLength);
		pData++;
		nLength--;
	}
}

int findMinDataIndex(const int* pData, int nLength)
{
	int nMinDataIndex = 0;

	for (int i = 1; i < nLength; i++)
	{
		if(pData[nMinDataIndex] > pData[i])
			nMinDataIndex = i;
	}

	return nMinDataIndex;
}

void printData(const int* pData, int nLength)
{
	for (int i = 0; i < nLength; i++)
	{
		printf("%d, ", pData[i]);
	}
	printf("\n");
}

void swapData(int& nDst, int& nSrc)
{
	int nTmp = nDst;
	nDst = nSrc;
	nSrc = nTmp;
}

 

 

3. 삽입 정렬 

3.1 핵심 로직

• 정렬된 배열에 데이터를 꽂는것 
  - 범위가 큰 동안에만
  - 인덱스가 0 이상일 경우에만
  - 백업하고 뒤로 복사

#include <iostream>

void insertionSortLogic(int* pData, int nLength);
void printData(const int* pData, int nLength);

int main()
{
    int arData[6]{2,3,4,5,6,1};
    insertionSortLogic(arData, 6);
    printData(arData, 6);
}

void insertionSortLogic(int* pData, int nLength)
{
    int nIndex = nLength - 2;
    int nData = pData[nLength - 1];

    while (nIndex >= 0 && pData[nIndex] > nData) // 반대는 터지는 코드다 
    {
        pData[nIndex + 1] = pData[nIndex];
        nIndex--;
    }
    pData[nIndex + 1] = nData;
}



void printData(const int* pData, int nLength)
{
    for (int i = 0; i < nLength; i++)
    {
        printf("%d ", pData[i]);
    }
    printf("\n");
}

 

4. 빅 오 표기법 

 

4.1 시간 복잡도 표기법

• 빅 오 표기법  : 알고리즘 최악의 실행 시간을 표기한다. 가장 많이 사용하는 표기법으로 최소한 보장되는 성능을 표기하기 떄문에 가장 일반적으로 사용됨
• 빅 오메가 표기법 : 표기법 알고리즘 최상의 실행 시간을 표기한다
• 빅 세타 표기법 : 알고리즘 평균 실행 시간을 표기한다.

4.2 빅 오 표기법 특징 

 

시간복잡도에 미미한 영향을 주는 것들은 배제하고 표기된다.

1. 상수항을 무시 
   어떤 알고리즘이 O(N+5)의 복잡도를 가졌으면 상수를 생략해 O(N)으로 표기한다
2. 계수도 무시
   어떤 알고리즘이  O(3N) 의 복잡도를 가졌으면 계수를 생략해 O(N)으로 표기한다
3. 최고차항만 표기 
   어떤 알고리즘이 O(3N^3+2N^2+N+5)의 복잡도를 가졌으면 O(N^3)으로 표기한다

4.3 빅 오 표기법 종류

 

1. O(1) : 스택에서 Push, Pop

2. O(log n) : 이진트리

3. O(n) : for 문

4. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)

5. O(

): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)

6. O(

) : 피보나치 수열

 

1 > 2 > 3 > 4 -> 5 > 6 /  상수함수 < 로그함수 < 선형함수 < 다향함수 < 지수함수