DEV Community: Aditi Jha

PANCAKE SORTING

Aditi Jha — Sat, 20 Feb 2021 08:40:19 +0000

Pancake sort is a sorting algorithm in which the only allowed operation is to "flip" one end of the list. It is inplace but not stable.

Just like the name, it means the same as sorting pancakes on a plate with a spatula, where you can only flip some of the top pancakes in the plate using spatula.

Given an unsorted array, sort the given array. You are allowed to do only following operation on array:

flip(arr, n): Reverse array from 0 to n

Our aim is to sort the sequence in as few reversals as possible i.e. shortest ways possible.

Explanation

The idea is to do something similar to Selection Sort. We one by one place maximum element at the end and reduce the size of current array by one.

Let given array be arr[] and size of array be i.

Start from current size equal to n and reduce current size by one while it’s greater than 1. Let the current size be current_size. Do the following for every current_size

▪︎ Find index of the maximum element in arr[0..current_size-1]. Let the index be ‘mid’
▪︎Call flip(arr, mid)
▪︎Call flip(arr, current_size-1)

# program to sort array using pancake sort
# Reverses arr[0..n] */

def flip(arr, n):
    start = 0
    while start < n:
        temp = arr[start]
        arr[start] = arr[n]
        arr[n] = temp
        start += 1
        n -= 1

# to return index of the maximum

def findMax(arr, i):
    mid = 0
    for i in range(0,i):
        if arr[n] > arr[mid]:
            mid = i
    return mid
#Main function
def pancakeSort(arr, i):
# Starting from the main array

    current_size = i
    while current_size > 1:
# Find index of the maximum element

        mid = findMax(arr, current_size)

#then current size is reduced one by one
# maximum element is moved to the end

        if mid != current_size-1:
# To move at the end, we first move maximum number to the beginning

            flip(arr, mid)
#now we reverse the array and maximum element is moved to the end

            flip(arr, current_size-1)
        current_size -= 1
# Function to print an array of size i

def printArray(arr, i):
    for i in range(0,i):
        print ("%d"%( arr[n]),end=" ")

# Driver program 
arr = [8,6,3,2,5,9,1,4,7,10]
i = len(arr)
pancakeSort(arr, i);
print ("The Sorted Array is")
printArray(arr,i)

Output:
The Sorted Array is: 1 2 3 4 5 6 7 8 9 10

Time Complexity: O(nlogn)

Applications

Pancake sorting appears in applications in parallel processor networks, it provides an effective routing algorithm between processors.
It is used when the only allowed operation to sort a sequence is reversing.

Lists in Python Part-2

Aditi Jha — Mon, 15 Feb 2021 08:42:18 +0000

Operations and Methods on Lists

Python has a lot of list methods that allow us to work with lists. Some of the methods are:
Python List append()- The append() method adds an item to the end of the list. The syntax of the append() method is: list.append(item). The method takes a single argument.

# names list
names = ['adi', 'prerna', 'ram']
# 'shyaam' is appended to the names list
names.append('shyaam')
# Updated namess list
print('Updated names list: ',names)

Output: ['adi', 'prerna', 'ram', 'shyaam']

Python List extend()- The extend() method adds all the elements of an iterable (list, tuple, string etc.) to the end of the list. The syntax of the extend() method is: list1.extend(iterable).

languages = ['Hindi', 'English']
# another list of language
languages1 = ['Bengali', 'Tamil']
# appending language1 elements to language
languages.extend(languages1)
print('Languages List:', languages)

Output: Languages List: ['Hindi', 'English', 'Bengali', 'Tamil']

Python List insert()- The list insert() method inserts an element to the list at the specified index. The syntax of the insert() method is: list.insert(i, a). Here, a is inserted to the list at the ith index. All the elements after ‘a’ are shifted to the right.

# vowel list
vowel = ['a', 'e', 'i', 'u']
# 'o' is inserted at index 3
# the position of 'o' will be 4th
vowel.insert(3, 'o')
print('Updated List:', vowel)

Output: Updated List: ['a', 'e', 'i', 'o', 'u']

Python List remove()- The remove() method removes the first matching element (which is passed as an argument) from the list. The syntax of the remove() method is: list.remove(element). The remove() method takes a single element as an argument and removes it from the list. If the element doesn't exist, it throws ValueError: list.remove(x): x not in list exception.

# animals list
animals = ['cat', 'dog', 'rabbit', 'guinea pig']

# 'rabbit' is removed
animals.remove('rabbit')

# Updated animals List
print('Updated animals list: ', animals)

Output:Updated animals list: ['cat', 'dog', 'guinea pig']

Python List pop()- The pop() method removes the item at the given index from the list and returns the removed item. The syntax of the pop() method is: list.pop(index). The method takes a single argument.

list1 = [ 1, 2, 3, 4, 5, 6 ] 
# Pops and removes the last element from the list 
print(list1.pop()) 
# Print list after removing last element 
print("New List after pop : ", list1, "\n") 
list2 = [1, 2, 3, ('cat', 'bat'), 4] 
# Pop last two element 
print(list2.pop()) 
print(list2.pop())
print(list2.pop())
# Print list 
print("New List after pop : ", li)

Output: 6
New List after pop : [1, 2, 3, 4, 5]
4
('cat', 'bat')
3
New List after pop : [1, 2]

Python List reverse()- The reverse() method reverses the elements of the list. The syntax of the reverse() method is: list.reverse(). It doesn't return any value, it just updates the existing list.

# fruits List
fruits = ['apple', 'banana', 'orange']
print('Original List:', fruits)
# List Reverse
fruits.reverse()
# updated list
print('Updated List:', fruits)

Output: Original List: ['apple', 'banana', 'orange']
Updated list: ['orange', 'banana', 'apple']

Python List Clear()- The clear() method removes all items from the list. The syntax of clear() method is: list.clear().

# Defining a list
list = [{1, 2}, ('a'), ['1.1', '2.2']]
# clearing the list
list.clear()
print('List:', list)

Output: List: []

Python List sort()- The sort() method sorts the elements of a given list in a specific ascending or descending order. The syntax of the sort() method is: list.sort(key=..., reverse=...). Alternatively, you can also use Python's built-in sorted() function for the same purpose. The syntax is: sorted(list, key=..., reverse=...).

# vowels list
vowels = ['e', 'a', 'u', 'o', 'i']
# sort the vowels
vowels.sort()
# print vowels
print('Sorted list:', vowels)

Output: Sorted list: ['a', 'e', 'i', 'o', 'u']

The simplest difference between sort() and sorted() is: sort() changes the list directly and doesn't return any value, while sorted() doesn't change the list and returns the sorted list.

Built-In functions of the Lists

len()- returns the length of the list. Syntax: list.len()
sum()- returns the sum of the numbers in the list. Syntax: list.sum()
insert()- Inserts object obj into list at offset index. Syntax: list.insert(index, obj)
count()-Returns count of how many times obj occurs in list. Syntax: list.count(obj)
max()- Returns item from the list with max value. Syntax: list.max()
min()- Returns item from the list with min value. Syntax: list.min()

Lists in python is a very important concept which plays an important role while learning the basics of python programming. Python programming language has many out of the box features, with the applications and implementations it has become one of the most popular programming language nowadays.

Find the part-1 of this blog here.

Lists in Python Part-1

Aditi Jha — Mon, 15 Feb 2021 07:38:13 +0000

Python is a simple, open-source and object-oriented coding language. It's easy to learn and fun, and its syntax is simple yet elegant. It is a popular choice for beginners, and is powerful enough to back some of the world’s most popular products and applications from companies like Google, Facebook, Spotify, Instagram and various others. Whatever the goal is, Python’s design makes the programming experience feel almost as natural as writing in English.

Data Types in Python
Python has six standard Data Types. They are:

Numbers
String
List
Tuple
Set
Dictionary

Lists in Python
A list is a collection of data within square brackets and with comma- separated values. A list is mutable, which means we can modify the list.
The best thing about a list is that items in a list need not be of the same type.

Ex: [1, "abc", 98, 20.6]

A List which does not contain any values within the square brackets is known as Empty List.

Properties of Lists

Lists are ordered: This means that the items have a defined order, and the order will not change. If we want to add any new element to the list, those elements will be added to the end of the list.
Lists can contain any arbitrary objects: A list can contain any amount of elements from 0 to the memory capacity of the device. The elements can be of various data types right from integer to string, float, etc.
List elements can be accessed by index: If you want to access any element of your list, you must write your list name followed by the index number in square brackets. Remember, Python is a zero indexed language, so indexing will start from Zero. Also, a negative list index counts from the end of the list.
Lists are mutable: A list is mutable, which means we can modify the list.
Lists Can Be Nested: A list can contain sublists, which in turn can contain sublists themselves, and so on to arbitrary depth. 6.Lists Allow Duplicate Values: Since lists are indexed, lists can have items with the same value.

How to create a list?
Lists are created using square brackets. Whatever elements we want to create a list with, we just put those elements in square brackets separated with commas.

#Create a list with elements 1, 2, Sea, 23.8.
my_list= [1, 2, "Sea", 23.8]

Output: 1, 2, Sea, 23.8

Creating a list with multiple distinct or duplicate elements
A list may contain duplicate values with their distinct positions and hence, multiple distinct or duplicate values can be passed as a sequence at the time of list creation.

list1= [1, 2, 4, 4, 3, 3, 3, 6, 5]
print(list1)

Output: 1,2,4,4,3,3,3,6,5

Accessing the elements of a list
There's no use of creating a list if we can't access those elements. Simplest way to access an element in a list is to write the list name and then the position of the element.

list1= [1, 2, 3, 4, 5, 6, 7];
print(list1[3])

Output: 4

Negative Indexing
We can also do negative indexing lists. The index of -1 refers to the last item, -2 to the second last item and so on.Negative indices are counted from the end of the list.

list1= [1, 2, 3, 4, 5, 6, 7];
print(list1[-1])

Output: 7

Accessing multiple elements of a list
We can access a range of items in a list by using the slicing operator : (colon). So if we want to access a range, we need two indices that will slice that portion from the list.
If we want to access a range, we need two indices that will slice that portion from the list.

b = "Hello, World!"
print(b[-5:-2])

Output: orl

For the Operation and Methods of lists, please refer the part-2 of this Blog.