Sort Array in Python
Learn via video course
FreeOverview
Array in python is similar to other data structures that are available in python like lists and tuples. An array contains similar data type elements. This property of array in python makes it different from lists and tuples. By default in python, the size of an array i.e. list is dynamic, it can either be increased or decreased at any point in time. For sorting the array in python, we can either use the inbuilt sort function available in python or we can create separate sort functions like insertion sort, bubble sort, or selection sort.
Scope
- In this article, we will be discussing how to sort the array in python using the inbuilt sort function
- We will also be discussing insertion sort, bubble sort, and selection sort.
- We will not be discussing the code of merge sort, bubble sort, and quick sort.
How to Sort an Array in Python?
Before we deep dive into sorting part of an array. Let me help you and tell you one most important thing is in python there is no direct method to sort an array. First of all, we have to import the array package in python to make our array, then we have to call our defined sort algorithms like merge sort or quick sort or we can use the inbuilt sorted function available in python (Will be explained in further part).
There are various algorithms available for sorting an array in python. Various sorting algorithms like:
- Bubble Sort
- Insertion Sort
- Selection Sort
- Merge Sort
- Quick Sort and much more.
Above mention algorithms are user-driven algorithms but python provides an inbuilt sorted() method to sort a list. In python numpy package also provides a sort function that helps us to sort an array(in-place).
Note: In-place means if we define a list or an array, it will not create an extra memory. It will do operations within the same list or an array. No other list or array is being created.
Using sorted() Function
Python uses extremely efficient algorithms to perform sorting in python. The sorted() method uses the Timsort algorithm which is the combination of Merge Sort and Quick Sort for performing highly optimized sorting.
Merge Sort
Merge Sort is one of the best algorithms for sorting an array in python. It uses the bottom-up Divide and Conquers approach.
Steps for this Algorithm:
- First divide the array into 2 sub-arrays.
- Sort those sub-arrays.
- Finally merge both the sub-arrays to get the sorted array.
Quick Sort
This algorithm uses the top-down Divide and Conquer approach. It is also one of the best algorithms to sort arrays in python, and it is the most widely used algorithm to sort arrays in python because of its space and time complexity.
Steps for this Algorithm:
- Select the pivot element (prefer to choose the last element of the array).
- Partition the array around the pivot element (such that elements less than the pivot will be on the left and elements greater than the pivot are on the right side). It will place the pivot element in its correct sorted position.
- Now we have created 2 sub-arrays one is right to pivot element and the other is left to pivot. Now follow steps 1 and 2 until we get all the elements at their respective position.
Note: There are other approaches to this algorithm for choosing the pivot element. Some variants choose the median element as the pivot, while others make use of a random selection strategy for the pivot.
Python code using the sorted function for sorting
Output:
Explanation: In the above code, a list l1 is created and is passed through a function sort_array.
What the sort_array function do is, first convert the list into an array(line 10), and then we sort that array using the sorted function that is available in python(line 19).
Note 1: The difference between a list and an array is list can contain multiple data types, but in an array, the data type of each element must be the same.
Note 2: To know more about the sorted function, Visit Here
Python code using sort function for sorting
Input:
Output:
Explanation: The above piece of code, uses the sort() function to sort the list(not array). A list of numbers is created and is sorted in ascending using the sort() function.
Using Selection Sort
The selection sort algorithm sorts an array by repeatedly finding the minimum element from the unsorted array. Then the minimum element is placed at the beginning() of the array.
For more details on Selection Sort, Visit Here
Input:
Output:
Using Insertion Sort
It is one of the simplest sorting algorithms that works similar to the way the deck of cards is being sorted.
In this algorithm, the array is split into a sorted part and an unsorted part. From the unsorted part of the array, the values are picked and placed at their correct position in the sorted part.
For more details on Insertion Sort, Visit Here
Input:
Output:
Using Numpy Sort Function
ALthough python has in-built sort and sorted functions to deal with sorting arrays. But in this section, we will much faster way to sort an array using the numpy module. NumPy's np. sort function turns out to be much more efficient and useful for our purposes. By default np. sort uses an O[NlogN], quicksort algorithm, though mergesort and heapsort are also available. For most applications, the default quicksort is more than sufficient.
Input:
Output:
Explanation:
Step 1: Create a list of element
Step 2: First convert the list into a NumPy array.
Step 3: Call the sort function available in NumPy to sort the array.
Step 4: Print the sorted NumPy array.
Conclusion
- In this article, we have how to sort an array.
- We went through various sorting methods like selection sort, and insertion sort.
- We have seen python in-built function sort and sorted. sorted function uses the Timsort algorithm which is the combination of merge sort and quick sort.
- At last, we have seen the np. sort function to sort the array. We have seen the sort and sorted function codes.