• Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard
CSEstack

What do you want to Learn Today?

  • Programming
    • Tutorial- C/C++
    • Tutorial- Django
    • Tutorial- Git
    • Tutorial- HTML & CSS
    • Tutorial- Java
    • Tutorial- MySQL
    • Tutorial- Python
    • Competitive Coding Challenges
  • CSE Subject
    • (CD) Compiler Design
    • (CN) Computer Network
    • (COA) Computer Organization & Architecture
    • (DBMS) Database Management System
    • (DS) Data Structure
    • (OS) Operating System
    • (ToA) Theory of Automata
    • (WT) Web Technology
  • Interview Questions
    • Interview Questions- Company Wise
    • Interview Questions- Coding Round
    • Interview Questions- Python
    • Interview Questions- REST API
    • Interview Questions- Web Scraping
    • Interview Questions- HR Round
    • Aptitude Preparation Guide
  • GATE 2022
  • Linux
  • Trend
    • Full Stack Development
    • Artificial Intelligence (AI)
    • BigData
    • Cloud Computing
    • Machine Learning (ML)
  • Write for Us
    • Submit Article
    • Submit Source Code or Program
    • Share Your Interview Experience
  • Tools
    • IDE
    • CV Builder
    • Other Tools …
  • Jobs

Complete Python Selection Sort Algorithm | Code Complexity

Aniruddha Chaudhari/28029/2
CodePython

As we know, sorting is a technique to arrange the elements in the array either in ascending or descending order. And there are multiple sorting algorithms such as bubble sort, insertion sort, quick sort, selections sort…

Here we will see Python selection sort.

Table of Contents

  • What is Selection Sort Algorithm?
  • Selection Sort in Python
  • Time Complexity of Selection Sort
  • Memory Complexity of Selection Sort

Before writing the code…

What is Selection Sort Algorithm?

Here is pseudo-algorithm for selection sorting.

  • Take the array (containing elements to sort) as an input
  • Iterate through all the elements in the array (says element as i)
  • Find the smallest elements from rest of the array (array elements next to i’s)
  • Swap the smallest element with i

If you understand the pseudo-algorithm, I would like if you minimize the browser and try to write code yourself.

Python Selection Sort Program

#swap two elements in nArr at postion i and j
def swap(i, j, nArr):
    if i!=j:     
        temp = nArr[j]
        nArr[j] = nArr[i]
        nArr[i] = temp

#function to sort elements in the list
def selectionSort(nArr):    
    for i in range(0, len(nArr)):
        small = i
        for j in range(i+1, len(nArr)):
            if nArr[j] < nArr[small]:
                small = j
        swap(i, small, nArr)

#list containing elements to sort        
nArr = [34,456, 5, 5,67]
selectionSort(nArr)
print(nArr)

Here in the above program, I have a hardcoded list. You can even take the list elements as user input.

Output:

[5, 5, 34, 67, 456]

In the first pass, the first element in the array will be in sorted position. After the second pass, two elements in the array will be sorted.

Likewise…

If you have n elements, after n-1 pass, n-1 elements will be sorted. If you arrange first n-1 elements in the array in the right position, the last element automatically will be in the right position.

So in each pass, you need to swap the elements at most one time. So in selection sort, you need a maximum n-1 pass and so the swaps to sort all the elements in the array.

If you compare with the bubble sort, in every pass we swap the elements multiple times. So you can consider the selection sort as improvement in bubble sort.

Above code, sort the elements in ascending order. If you want the same program to sort elements in descending order, replace < with > inside the function selectioSort().

For sorting, you need to take Numeric data types values. Just to give little tweak, you can also use a list containing characters to sort.

Time complexity of Selection Sort

As you have to compare each element with other elements from an array list, it has a time complexity of o(n^2) in all three cases (best, average and worst case).

As it takes O(n^2) time, it is not considered as an efficient algorithm for sorting if you have minimal time.

Memory Complexity of Selection Sort

Selection sort does not require any extra memory (except for swapping). So, it takes constant time O(1), despite the number of elements in the array.

You need to swap the elements, only if it is required. If your array is already sorted, there will be zero numbers of swapping.

Just to clarify…

Here we are using the list to sort. As tuple is an immutable data structure in Python, you can not use tuple for sorting. For more, you can read List vs Tuple in Python.

If you understand the logic behind Python selection sort, it is easy to implement in any programming language. Any doubt? Write in the comment section.

Python Interview Questions eBook

Python
Aniruddha Chaudhari
I am complete Python Nut, love Linux and vim as an editor. I hold a Master of Computer Science from NIT Trichy. I dabble in C/C++, Java too. I keep sharing my coding knowledge and my own experience on CSEstack.org portal.

Your name can also be listed here. Got a tip? Submit it here to become an CSEstack author.

Comments

  • Reply
    Salim Wakar
    February 1, 2020 at 4:16 pm

    Thanks for giving this simple explanation. I came here while searching for help for my assignment. Learning data structures with Python is fun especially we have to write really few lines of code.

    • Reply
      Aniruddha Chaudhari
      February 1, 2020 at 7:22 pm

      You’re welcome, Salim. I hope you found whatever you were looking for your assignment.

Leave a Reply Cancel reply

Basic Python Tutorial

  1. Python- Tutorial Overview
  2. Python- Applications
  3. Python- Setup on Linux
  4. Python- Setup on Windows
  5. Python- Basic Syntax
  6. Python- Variable Declaration
  7. Python- Numeric Data Types
  8. Python- NoneType
  9. Python- if-else/elif
  10. Python- for/while else
  11. Python- User Input
  12. Python- Multiline User Input
  13. Python- String Formatting
  14. Python- Find Substring in String
  15. Python- Bitwise Operators
  16. Python- Range Function
  17. Python- List
  18. Python- List Vs Tuple
  19. Python- Compare Two Lists
  20. Python- Sorting List
  21. Python- Delete Element from List
  22. Python- Dictionary
  23. Python- ‘is’ vs ‘==’
  24. Python- Mutable vs Immutable
  25. Python- Generator & Yield
  26. Python- Fibonacci Generator
  27. Python- Assert Statement
  28. Python- Exception Handling 
  29. Python- RegEx
  30. Python- Lambda Function
  31. Python- Installing Modules
  32. Python- Important Modules
  33. Python- Find all Installed Modules
  34. PyCharm- IDE setup
  35. Python- File Handling
  36. Python- Monkey Patching
  37. Python- Decorators
  38. Python- Instance vs Static vs Class Method
  39. Python- Name Mangling
  40. Python- Working with GUI
  41. Python- Read Data from Web URL
  42. Python- Memory Management
  43. Python- Virtual Environment
  44. Python- Calling C Function

Python Exercise

  1. Python- Tricky Questions
  2. Python- Interview Questions (60+)
  3. Python- Project Ideas (45+)
  4. Python- MCQ Test Online
  5. Python- Coding Questions (50+)
  6. Python- Competitive Coding Questions (20+)

Python String

  1. Reverse the String
  2. Permutations of String
  3. Padding Zeros to String/Number

Python List

  1. Randomly Select Item from List
  2. Find Unique Elements from List
  3. Are all Elements in List Same?

Python Dictionary

  1. Set Default Value in Dictionary
  2. Remove all 0 from a dictionary

File Handling

  1. Python- Read CSV File into List
  2. Check if the File Exist in Python
  3. Find Longest Line from File

Compilation & Byte Code

  1. Multiple Py Versions on System
  2. Convert .py file .pyc file
  3. Disassemble Python Bytecode

Algorithms

  1. Sorting- Selection Sort
  2. Sorting- Quick Sort

Other Python Articles

  1. Clear Py Interpreter Console
  2. Can I build Mobile App in Python?
  3. Extract all the Emails from File
  4. Python Shell Scripting

© 2022 – CSEstack.org. All Rights Reserved.

  • Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard