top of page

Selection sort

The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.


Example:


arr[] = 64 25 12 22 11 // Find the minimum element in arr[0...4] // and place it at beginning 11 25 12 22 64 // Find the minimum element in arr[1...4] // and place it at beginning of arr[1...4] 11 12 25 22 64 // Find the minimum element in arr[2...4] // and place it at beginning of arr[2...4] 11 12 22 25 64 // Find the minimum element in arr[3...4] // and place it at beginning of arr[3...4] 11 12 22 25 64


def selection_sort(A):
    # Find the minimum element in remaining
    # unsorted array 
    for i in range(len(A)): 
        min_idx = i
        for j in range(i + 1, len(A)):
            if A[min_idx] > A[j]:
                min_idx = j

            # Swap the found minimum element with  
            # the first element         
        A[i], A[min_idx] = A[min_idx], A[i] 
    


Recent Posts

See All

Linear search

A linear search is used on a collection of items. It relies on the technique of traversing a list from start to end by exploring properties of all the elements that are found on the way. For example,

Dynamic programming introduction

If break up a problem into a series of overlapping sub-problems, and build up solutions to larger and larger sub-problems. If a problem can be broken down into smaller sub-problems, and these smaller

Comentarios


bottom of page