[go: up one dir, main page]
Scribd
Upload
40 views5 pages

Selection Sort

This document contains instructions for a lab assignment to implement selection sort in Python. Selection sort works by iteratively finding the minimum element in a sublist and swapping it into the sorted position. The algorithm has O(n2) time complexity. It provides pseudocode steps for selection sort, including initializing an index i, finding the minimum element in the sublist from index i to the end, swapping it with the element at index i, and incrementing i until the list is fully sorted. The document also includes Python code that implements selection sort on a sample list.

Uploaded by

Muhammad Umar
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
40 views5 pages

Selection Sort

This document contains instructions for a lab assignment to implement selection sort in Python. Selection sort works by iteratively finding the minimum element in a sublist and swapping it into the sorted position. The algorithm has O(n2) time complexity. It provides pseudocode steps for selection sort, including initializing an index i, finding the minimum element in the sublist from index i to the end, swapping it with the element at index i, and incrementing i until the list is fully sorted. The document also includes Python code that implements selection sort on a sample list.

Uploaded by

Muhammad Umar
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
You are on page 1/ 5

Practical Workbook

Data Structure and Algorithm

STUDENT NAME: ______________________________________

STUDENT ID: ______________________________________

SECTION: ______________________________________

Signature of Faculty: ______________________________________

SMIU
Department of Computer Science
LAB # 11
Sorting a list using selection sort in Python
Selection sort is one of the simplest sorting algorithms. It is similar to the hand
picking where we take the smallest element and put it in the first position and
the second smallest at the second position and so on. It is also similar. We first
check for smallest element in the list and swap it with the first element of the
list. Again, we check for the smallest number in a sublist, excluding the first
element of the list as it is where it should be (at the first position) and put it in
the second position of the list. We continue repeating this process until the list
gets sorted.

The time complexity of selection sort is (O(n2)).

We follow the following steps to perform selection sort:

1. Start from the first element in the list and search for the smallest element
in the list.
2. Swap the first element with the smallest element of the list.

3. Take a sublist (excluding the first element of the list as it is at its place)


and search for the smallest number in the sublist (second smallest number
of the entire list) and swap it with the first element of the list (second
element of the entire list).

4. Repeat the steps 2 and 3 with new sublists until the list gets sorted.

Working of selection sort:


First, we’ll create a recursive method to do the selection:

a = [16, 19, 11, 15, 10, 12, 14]

i = 0
while i<len(a):
#smallest element in the sublist
smallest = min(a[i:])
#index of smallest element
index_of_smallest = a.index(smallest)
#swapping
a[i],a[index_of_smallest] = a[index_of_smallest],a[i]
i=i+1
print (a)

Output:
[10, 11, 12, 14, 15, 16, 19]
Explanation of code:

The code is just an implementation of the above explanation. We are finding


the smallest number by using the ‘min’ function. and then swapping it with
the first element of the sublist. You can see this article for the list of the
functions available on a Python’s list.

You might also like