[공학]데이터구조 자바로 구현한 쉘 정렬 버블flag사용 정렬 퀵 정렬 완벽 문서정리 및 스크린캡춰

소개

자바로 구현한 버블 , 쉘 , 퀵 정렬 이다
데이터구조 책 3권을 참고하여 심도있게 접근 하였으며
버블 정렬의 경우 이미 정렬이 완료되어도 n-1번까지 정렬하는 과정을 제거하기위하여
flag를 사용하였으며 do-while문으로 for문을 한번만 사용하였다.

다음은 본문에서 발췌한 설명글이다.
수행과제. Flag를 사용하고 버블 정렬 시 for문을 한번만 사용하여 이를 구현하라.
해결을 위해 행했던 수순.
1. 자바언어와 씨 언어를 사용한 알고리즘 서적 3권을 참고하여 버블정렬의 개념을 익힘.
2. for문 두 개를 이용하여 버블정렬을 구현 한 다음 두 개의 for문중 어떤 for문을 flag로 대체할 수 있을가를 고민함
3. 두 개의 for문 가운데에 인접한 값을 비교하는 for문을 살려두고 비교해야 할 전체 사이즈를 정하는 for문을 flag로 대체해야 겠다는 아이디어를 떠올림
4. 3 단계의 아이디어는 if문이나 for문 또는 while문에서 하나의 조건(식)을 항상 참으로 두면, 그 문장의 범위내에서는 그 조건으로 주어진 값이 거짓이 될 때까지 무한 루프를 실행된다는 발상에서 착안하였음.
5. 처음에는 if문의 조건에 flag를 두고 해결해 보려 했으나, 조건의 영향을 받는 중괄호의 범위와 flag값을 참으로 변화시킬 문장의 위치를 아무리 달리 해봐도 array[i]번째 값 하나만 원하는 위치로 옴겨지거나, 입력되는 값이 특정한 값일때에 제대로 동작하지 않음을 확인 하였음.
6. 따라서, if문이 아니라 처음 초기값을 줄 수 있고 조건식을 함께 정할수 있는 do-while로 대체하여 입력값을 넣으니 5 단계에서 발생하였던 문제가 해결되었고 원하는 결과값을 얻을 수 있었음.

목차

자바로 구현한 정렬 3가지(버블,퀵,쉘)

1. 버블 정렬
1-1 버블정렬 소스
1-2 버블정렬 실행화면
1-3 정리

2. 퀵 정렬
2-1 퀵정렬 소스
2-2 퀵정렬 실행화면
2-3 정리

3. 쉘 정렬
3-1 쉘정렬 소스
3-2 쉘정렬 실행화면
3-3 정리

본문내용

버블 정렬의 특성 중 하나는 이해하기 쉽고 프로그램을 작성하기 쉽다는 점이다. 그러나 가장 비효율적인 정렬이기도 하다. 버블 정렬을 수행하는 기본적인 아이디어는 파일을 순차적으로 여러 번 패스하는 것이다. 각 패스는 파일 안에 있는 각 요소들을 다음 요소와 비교해(x[i]와 x[i+1])적절한 순서가 아니면 두 요소를 교환한다. 연속되는 키 값들을 비교하는데, 첫 번째 값인 1과 두번째 값인 6을 오름 차순에 맞게 위치를 바꾸어 주고 다음으로 두 번째 값인 바뀐 10과 세번쨰 값인 22를 비교해준다. 이런 비교 – 교환 작업을 (n-1)회 반복하면 가장 큰 값인 100이 제일 마지막에 위치하게 된다. 각 단계별로 (n-k)번씩의 비교를 하게되며 최대 n-1번의 단계를 거쳐서 정렬된 값을 얻게 된다.(k : k 번쨰 단계)

쉘 정렬의 특성
쉘 정렬은 버블 정렬의 단점인 정렬하고자 하는 위치에서 멀리 떨어진 항목이 정렬되기 위해서는 계속적인 교환이 발생하여야 한다는 단점을 극복하여 성능을 향상시키고 삽입 정렬의 장점인 어느 정도 정렬된 배열에서 높은 정렬 수행속도를 가지는 장점을 잘 이용한 정렬이라 할 수 있다.

퀵 정렬은 1962년에 C.A.R Hoare가 만든 정렬 알고리즘이다. 퀵 정렬은 정렬 알고리즘 중 가장 우수한 평균 수행속도를 가진다. 그래서 현재까지 가장 유명한 정렬 알고리즘으로 알려져 있다. 이러한 퀵 정렬은 분할 알고리즘(partition algorithm)을 기본 개념으로 하고 있다. 따라서 분할 알고리즘에 대해서도 알아야 한다.

참고자료

· 자바로 구현한 데이터구조