Scribd
Upload
2 views3 pages

Program 5

The document outlines the Selection Sort algorithm, which involves finding the minimum element in an unsorted array and swapping it with the current position, repeating this process until the array is fully sorted. It includes a code implementation in Java and details the time complexity for best, average, and worst cases, all of which are O(n²), while the space complexity is O(1). The algorithm performs a fixed number of comparisons regardless of the initial order of the array.

Uploaded by

preetimandal7777
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2 views3 pages

Program 5

The document outlines the Selection Sort algorithm, which involves finding the minimum element in an unsorted array and swapping it with the current position, repeating this process until the array is fully sorted. It includes a code implementation in Java and details the time complexity for best, average, and worst cases, all of which are O(n²), while the space complexity is O(1). The algorithm performs a fixed number of comparisons regardless of the initial order of the array.

Uploaded by

preetimandal7777
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

PROGRAM 5 

SELECTION SORT 

ALGORITHM 

1. Initialize: Start with the first element of the array (position index 0).
Assume it is the minimum element.

2. Find Minimum: Traverse the unsorted portion of the array (from the
current position to the end) to find the actual minimum element.

3. Swap: Swap the minimum element found with the element at the
current position.

4. Move Boundary: Increment the starting point of the unsorted portion


by one, marking one more element as sorted.

5. Repeat: Repeat steps 2-4 until the entire array is sorted (i.e., until all
elements are in the sorted portion).

CODE 

class SelectionSortSimple {

public static void main(String[] args) {

int arr[] = {64, 25, 12, 22, 11};

int n = [Link];

// Selection Sort

for (int i = 0; i < n - 1; i++) {

int min = i; // assume current index is min

for (int j = i + 1; j < n; j++) {

if (arr[j] < arr[min]) {

min = j; // update min index

}
}

// swap

int temp = arr[i];

arr[i] = arr[min];

arr[min] = temp;

for (int x : arr) {

[Link](x + " ");

OUTPUT 

TIME AND SPACE COMPLEXITIES 


Case Time Explanation
Complexity

Algorithm still makes all comparisons even if arr


Best Case O(n²) is sorted.

Average Comparisons performed on a randomly ordered


Case O(n²) array.

Worst Occurs with array in descending order, same


Case O(n²) number of comparisons.

Other Metrics Complexity Notes

In-place sorting without extra


Space Complexity O(1) memory.

n(n−1)22n(n−
Number of Comparisons 1) Sum of comparisons in nested loo

You might also like