본문 바로가기

Data Structure

삽입 정렬 이번에 소개 드릴 삽입 정렬은 별도의 메모리를 필요로 하지 않는 '개선된 선택 정렬'과 유사하다고 느끼실 수 있습니다. 하지만 개선된 선택 정렬과는 전혀 다른 방법으로 정렬을 이뤄 나가는데 아래의 그림을 통해 설명해 드리도록 하겠습니다. 위 그림의 배열은 정렬이 완료된 부분과 그렇지 않은 부분으로 니뉘어져 있습니다. 즉 삽입 정렬은 정렬 대상을 두 부분 으로 나눠서, 정렬 안 된 부분에 있는 데이터를 정렬 된 부븐의 특정 위치에 '삽입'해 가면서 정렬을 진행하는 알고리즘입니다. 다음 그림을 통해 5, 3, 2, 4, 1의 오름차순 정렬과정을 보도록 합시다. 첫 번째 데이터와 두 번째 데이터를 비교하여, 정렬된 상태가 되도록 두 번째 데이터를 옮기면서 정렬이 시작됩니다. 그리고 이로 인해 첫 번째 데이터와.. 더보기
선택정렬 이번에는 버블 정렬보다 쉽고 간단한 알고리즘인 선택 정렬에 대하여 얘기를 하고자 합니다. 선택 정렬은 정렬 순서에 맞게 하나씩 선택해서 옮기는, 옮기면서 정렬이 되게하는 알고리즘인데요. 위 이미지에서 보이는 대로 정렬을 진행하면 별도의 메모리 공간이 필요하게 됩니다.. 하지만! 데이터를 하나 옮길 때마다 공간이 하나씩 비게 된다는 사실을 기반으로 아래와 같이 알고리즘을 개선시키면 별도의 메모리 공간을 마련할 필요가 없어집니다! 위의 이미지를 보시면 '교환'이라는 표현을 사용하고 있는데, 적절한 표현 방식은 아닙니다. 그래서 다음과 같이 이해할 필요가 있습니다."정렬순서상 가장 앞서는 것을 선택해서 가장 왼쪽으로 이동시키고, 원래 그 자리에 있던 데이터는 빈 자리에 가져다 놓는다."결론적으로 교환은 맞지만.. 더보기
버블 정렬 여러분들이 프로그래밍을 하시면서 한 번쯤은 들어봤을 법한 정렬방식 입니다. 바로 버블 정렬 이라는 방식인데요, 많이 들어본 이름인 만큼 구현하기도 쉽고, 이해하기도 쉽습니다만 구현과 이해가 쉬운만큼 성능에서는 조금 아쉬운 모습을 보여주지요. 아래의 이미지는 3, 2, 4, 1이 순서대로 저장된 배열을 오름차순으로 정렬하는 과정을 보여주고 있습니다. 이 이미지를 통해 버블 정렬의 과정을 소개하도록 할게요. 중간에 생략이 있긴한데, 대충 어떻게 비교되고 교환되는지 예상하실 수 있을거라 생각하고 뛰어 넘겼습니다. 위의 이미지를 보시면 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는데, 이게 버블정렬의 정렬 방식입니다. 두 데이터를 비교하여, 정렬 순서상 위치가 바뀌어야 하는 경우에 두 데이터의 위치를 바.. 더보기
원형 이중 리스트 main.cpp #include #include #include"List.h" int main() { List list; LData Data; LInit(&list); LInsert(&list, 1); LInsert(&list, 2); LInsert(&list, 3); LInsert(&list, 4); LInsert(&list, 5); printf("현재 데이터 수 : %d\n", LCount(&list)); if (LFirst(&list, &Data)) { printf("%d ", Data); for (int i = 0; i < (LCount(&list) * 3) - 1; i++) { if (LNext(&list, &Data)) { printf("%d ", Data); } } } int num = 0;.. 더보기

티스토리툴바