자료구조 (3) 썸네일형 리스트형 [자료구조] Linux Kernel Generic Swap 함수 분석 및 구현 일반적으로 사용하는 Swap 함수 #include void swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } int main(void) { int x = 1; int y = 2; swap(&x, &y); printf("x(%d), y(%d)\n", x, y); } 일반적으로 swap() 함수는 위의 코드와 같이 포인터를 사용해서 두 숫자를 바꿔줄 때 사용된다. 일반적인 swap 함수의 문제점 만약 그냥 swap 함수를 사용하게 된다면, 데이터 타입의 변경이 발생했을 때 각각의 타입에 맞춰서 함수를 구현해야하는 치명적인 문제점이 있다. #include void swap(int* a, int* b) { int tmp = *a; *a = *b; *b = t.. [자료구조] Select sort (선택 정렬) Select sort는 개념이 무척 간단하다. 오름차순의 경우 각 step마다 가장 큰 값을 찾아 제일 끝 요소와 자리를 바꾼다.내림차순의 경우 각 step마다 가장 큰 값을 찾아 제일 첫 요소와 자리를 바꾸면 된다. 그림으로 설명하자면 아래와 같다. STEP 1) 모든 요소를 검사하여 가장 큰 값을 array[max-1]에 저장한다.STEP 2) max-1 요소 전까지 검사하여 가장 큰 값을 array[max-2]에 저장한다.STEP 3) max-2 요소 전까지 검사하여 가장 큰 값을 array[max-3]에 저장한다. 선택 정렬의 경우 시간 복잡도는 O(n^2)이며, 알고리즘이 매우 단순하다.또한 메모리 이동이 적을 수 있어서 메모리가 제한적인 환경에서 사용하면 성능 상 유리하다. 코드는 아래와 같이.. [자료구조] Bubble sort (버블 정렬) 두 인접한 자료를 비교하여 앞의 데이터가 뒤의 데이터보다 크면 위치를 교환한다. 시간 복잡도는 O(n^2)로 상당히 느리지만, 코드가 단순하여 많이 사용된다.Bubble sort는 알고리즘 시험을 처음 준비할 때 오름차순 및 내림차순으로 정렬해야 할 문제들을 대비하기 위해 공부하였었는데, 결국 느린 시간복잡도로 인해 다른 정렬 방법으로 바꾼 기억이 난다. 그림으로 설명하자면 아래와 같다. STEP 1) 첫 요소부터 검사를 진행한다. 인접한 요소와 비교하면서 앞의 요소가 뒤의 요소보다 크면 위치를 교환한다.STEP 2) 진행STEP 3) 진행STEP 4) STEP 1과 같이 앞의 요소가 더 크기 때문에 위치를 교환한다.STEP 5) 1차 검사 완료 위의 STEP을 반복하며 진행되는데, 1차 검사가 arra.. 이전 1 다음
