selection sort java selection sort algorithm examples
이 튜토리얼은 선택 정렬 알고리즘, Java 코드, Java 구현 및 Java 예제와 함께 Java의 선택 정렬에 대한 모든 것을 설명합니다.
선택 정렬 기술은 배열에서 가장 작은 요소를 선택하고 배열의 첫 번째 요소로 교체하는 방법입니다. 다음으로 배열에서 두 번째로 작은 요소가 두 번째 요소와 교환되고 그 반대의 경우도 마찬가지입니다.
=> 여기에서 Java 교육 자습서의 A-Z를 보려면 여기를 확인하십시오.
학습 내용 :
자바에서 선택 정렬
이렇게하면 배열에서 가장 작은 요소가 반복적으로 선택되고 전체 배열이 정렬 될 때까지 적절한 위치에 배치됩니다.
선택 정렬을 위해 두 개의 하위 배열이 유지됩니다.
- 정렬 된 하위 배열 : 모든 반복에서 최소 요소를 찾아 적절한 위치에 배치합니다. 이 하위 배열이 정렬됩니다.
- 정렬되지 않은 하위 배열 : 정렬되지 않은 나머지 요소입니다.
선택 정렬은 간단하고 쉬운 정렬 기술입니다. 이 기술은 모든 패스에서 가장 작은 요소를 찾아 올바른 위치에 배치하는 것뿐입니다. 선택 정렬은 더 작은 데이터 세트를 효율적으로 정렬하므로 더 작은 데이터 세트에 이상적입니다.
따라서 더 큰 데이터 목록에는 선택 정렬이 권장되지 않는다고 말할 수 있습니다.
선택 정렬 알고리즘
선택 정렬을위한 일반 알고리즘은 다음과 같습니다.
선택 정렬 (A, N)
1 단계 : K = 1 ~ N-1에 대해 2 단계와 3 단계를 반복합니다.
2 단계 : 최소 호출 루틴 (A, K, N, POS)
3 단계 :
A (K)를 A (POS)로 교체
(루프 끝)
4 단계 : 종료
가장 작은 루틴 (A, K, N, POS)
1 단계 : (초기화) set smallestItem = A (K)
2 단계 : (초기화) POS = K 설정
3 단계 :
J = K + 1 ~ N -1 인 경우 반복
smallestItem> A (J) 인 경우
smallestItem = A 설정 (J)
POS = J 설정
(종료 된 경우)
(루프 끝)
4 단계 : 반품 POS
보시다시피 데이터 세트를 순회하는 동안 가장 작은 숫자를 찾는 루틴이 호출됩니다. 가장 작은 요소가 발견되면 원하는 위치에 배치됩니다.
C ++ 날짜 및 시간
선택 정렬을위한 의사 코드
선택 정렬 알고리즘의 의사 코드는 다음과 같습니다.
Procedure selection_sort(array,N) array – array of items to be sorted N – size of array begin for I = 1 to N-1 begin set min = i for j = i+1 to N begin if array(j) 이제 선택 정렬을 사용하여 배열 정렬을 설명하겠습니다.
선택 정렬 예
선택 정렬의 예로 정렬 될 다음 배열을 고려하십시오.
다음은 그림에 대한 표 형식입니다.
정렬되지 않은 목록 최소 요소 정렬 된 목록 {17,10,7,29,2} 두 {} {17,10,7,29} 7 {두} {17,10,29} 10 {2.7} {17.29} 17 {2,7,10) {29} 29 {2,7,10,17} {} {2,7,10,17,29}
그림에서 모든 패스에서 다음으로 가장 작은 요소가 정렬 된 배열의 올바른 위치에 배치되는 것을 볼 수 있습니다. 일반적으로 N 개의 요소 배열을 정렬하려면 총 N-1 개의 패스가 필요합니다.
Java에서 선택 정렬 구현
이제 선택 정렬을 구현하는 Java 프로그램을 시연 해 보겠습니다.
import java.util.*; class Main { static void sel_sort(int numArray()) { int n = numArray.length; // traverse unsorted array for (int i = 0; i 산출:
원래 배열 : (7, 5, 2, 20, 42, 15, 23, 34, 10)
정렬 된 배열 : (2, 5, 7, 10, 15, 20, 23, 34, 42)
위의 자바 예제에서는 배열에서 가장 작은 요소를 반복해서 찾아 전체 배열이 완전히 정렬 될 때까지 정렬 된 배열에 넣습니다.
Java에서 선택 정렬 링크 목록
아래에 연결된 목록이 있으며 선택 정렬을 사용하여 정렬해야합니다. 이를 위해 우리는 선택 정렬의 재귀 적 접근 방식을 사용할 것입니다. 노드의 데이터 부분을 교체하는 대신 노드를 교체하고 포인터를 재정렬합니다.
따라서 연결 목록이 다음과 같이 주어지면 :
아래는 위의 정렬을 구현하는 Java 프로그램입니다.
// add a node to the beginning of the linked list static Node addNode( Node head_ref, int new_data) { // create a node Node newNode = new Node(); // assign data to node newNode.data = new_data; // link the node to linked list newNode.next = (head_ref); //head now points to new node (head_ref) = newNode; return head_ref; } // method to swap nodes static Node swapNodes( Node head_ref, Node curr_node1, Node curr_node2, Node prev_node) { // curr_node2 is new head head_ref = curr_node2; // realign links prev_node.next = curr_node1; // now swap next pointers of nodes Node temp = curr_node2.next; curr_node2.next = curr_node1.next; curr_node1.next = temp; return head_ref; } // sort the linked list using selection sort static Node Selection_Sort( Node head) { // only a single node in linked list if (head.next == null) return head; // minNode => node with minimum data value Node minNode = head; // prevMin => node previous to minNode Node prevMin = null; Node ptr; // traverse the list from head to last node for (ptr = head; ptr.next != null; ptr = ptr.next) { // check if current node is minimum if (ptr.next.data 산출:
원본 링크 목록 :
7 9 3 5 1 11
정렬 후 연결된 목록 :
1 3 5 7 9 11
위의 프로그램에서는 노드의 데이터 구성 요소 만 정렬하는 대신 노드의 링크를 재정렬했습니다.
자주 묻는 질문
Q # 1) 선택 정렬은 어떻게 작동합니까?
대답: 선택 정렬은 두 개의 하위 배열을 유지하여 작동합니다. 정렬되지 않은 하위 배열의 최소 요소는 정렬 된 하위 배열의 적절한 위치에 배치됩니다. 그런 다음 두 번째로 낮은 요소가 적절한 위치에 배치됩니다. 이렇게하면 각 반복 중에 최소 요소를 선택하여 전체 배열이 정렬됩니다.
질문 # 2) 선택 정렬의 복잡성은 무엇입니까?
대답: 선택 정렬의 전반적인 복잡성은 O (n두), 따라서 더 큰 데이터 세트에서 비효율적 인 알고리즘이됩니다. 다른 정렬 기술이 더 효율적입니다.
질문 # 3) 선택 정렬의 장점과 단점은 무엇입니까?
대답: 선택 정렬은 내부 정렬 기술이므로 중간 요소를 저장하기 위해 추가 저장소가 필요하지 않습니다.
작은 데이터 구조와 거의 정렬 된 데이터 세트에서 효율적으로 작동합니다.
선택 정렬 기술의 주요 단점은 데이터 구조의 크기가 증가함에 따라 성능이 매우 저하된다는 것입니다. 속도가 느려질뿐만 아니라 효율성도 떨어집니다.
CPU 온도를 모니터링하는 최고의 프로그램
질문 # 4) 선택 정렬에는 몇 개의 스왑이 있습니까?
대답: 선택 정렬 기술은 최소 스왑 수를 사용합니다. 최상의 경우 배열이 정렬 될 때 선택 정렬의 스왑 수는 0입니다.
질문 # 5) 선택 정렬이 삽입 정렬보다 빠릅니까?
대답: 삽입 정렬은 더 빠르고 효율적이며 안정적입니다. 선택 정렬은 더 작은 데이터 세트와 부분적으로 정렬 된 구조에 대해서만 더 빠릅니다.
결론
선택 정렬은 배열을 순회하는 동안 최소 요소를 선택하여 작동하는 기술입니다. 각 통과 / 반복에 대해 데이터 세트의 다음 최소 요소가 선택되고 적절한 위치에 배치됩니다.
선택 정렬 기술은 데이터 세트의 요소 수가 적을 때 효율적으로 작동하지만 데이터 세트의 크기가 커짐에 따라 성능이 저하되기 시작합니다. 삽입 정렬과 같은 다른 유사한 기술과 비교할 때 비효율적입니다.
이 자습서에서는 선택 정렬을 사용하여 배열 및 연결 목록을 정렬하는 예제를 구현했습니다.
=> 모두를위한 Java 교육 시리즈를 보려면 여기를 방문하십시오.
추천 도서
