How do I alphabetically sort an array of strings without any sort functions? Python

Question

When solving the following problem: "Assuming you have a random list of strings (for example: a, b, c, d, e, f, g), write a program that will sort the strings in alphabetical order. You may not use the sort command."

I run into the problem of running strings through the following code, which sometimes gets me duplicated strings in final list

I am fairly new to python and our class just started to look at numpy, and functions in that module, and im not sure of any being used in the code (except any sort function).

import numpy as np

list=[]
list=str(input("Enter list of string(s): "))
list=list.split()
print() # for format space purposes
listPop=list
min=listPop[0]
newFinalList=[]

if(len(list2)!=1):
    while(len(listPop)>=1):
        for i in range(len(listPop)):
            #setting min=first element of list
            min=listPop[0]
            if(listPop[i]<=min):
                min=listPop[i]
                print(min)    
        listPop.pop(i)
        newFinalList.append(min)
    print(newFinalList)
else:
    print("Only one string inputted, so already alphabatized:",list2)

Expected result of ["a","y","z"]

["a","y","z"]

Actual result...

Enter list of string(s): a y z

a a a ['a', 'a', 'a']

Enter list of string(s): d e c

d c d d ['c', 'd', 'd']

This is definitely not going to be easy for a beginner, but here's something you can do. Make a Numpy array of letters letters = ['a', 'b', 'c'...]. Then, when you get a string, use np.where() or np.argwhere() to get the index of the letter ('a' will be 0, 'z' will be 25). Then, after getting the indices of two letters, you can determine which is smaller. If you don't need to use Numpy, you can use a string instead: letters = 'abcdef...'. Then, use letters.find('a') to get the index of the letter ('b' would be the second position). Once again, compare the indices. — Nicolas Gervais
– Nicolas Gervais, Commented Oct 30, 2019 at 3:47
I'm not sure if this is allowed but convert it to ascii code and work with numbers — user2755526
– user2755526, Commented Oct 30, 2019 at 3:50
Do they expect you to use numpy in this sorting? or is this sorting task left over from some unit that you studied before? — hpaulj
– hpaulj, Commented Oct 30, 2019 at 5:17

Samwise · Accepted Answer · 2019-10-30 04:42:26Z

1

Selection sort: for each index i of the list, select the smallest item at or after i and swap it into the ith position. Here's an implementation in three lines:

# For each index i...
for i in range(len(list)):
    # Find the position of the smallest item after (or including) i.
    j = list[i:].index(min(list[i:])) + i
    # Swap it into the i-th place (this is a no-op if i == j).
    list[i], list[j] = list[j], list[i]

list[i:] is a slice (subset) of list starting at the ith element.
min(list) gives you the smallest element in list.
list.index(element) gives you the (first) index of element in list.
a, b = b, a atomically swaps the values of a and b.

The trickiest part of this implementation is that when you're using index to find the index of the smallest element, you need to find the index within the same list[i:] slice that you found the element in, otherwise you might select a duplicate element in an earlier part of the list. Since you're finding the index relative to list[i:], you then need to add i back to it to get the index within the entire list.

edited Oct 30, 2019 at 4:42

answered Oct 30, 2019 at 4:15

Samwise

72.1k3 gold badges36 silver badges52 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Ryan Over a year ago

Could you add a little more explanation of how you're implementing this?

Divyesh patel · Accepted Answer · 2019-10-30 04:01:27Z

1

You can implement Quick sort for same:

def partition(arr,low,high): 
    i = ( low-1 )        
    pivot = arr[high]
    for j in range(low , high):     
        if arr[j] <= pivot:         
            i = i+1
            arr[i],arr[j] = arr[j],arr[i]
    arr[i+1],arr[high] = arr[high],arr[i+1] 
    return ( i+1 ) 

def quickSort(arr,low,high): 
    if low < high:      
        pi = partition(arr,low,high)        
        quickSort(arr, low, pi-1) 
        quickSort(arr, pi+1, high) 

arr = ['a', 'x', 'p', 'o', 'm', 'w'] 
n = len(arr) 
quickSort(arr,0,n-1) 
print ("Sorted list is:") 
for i in range(n): 
    print ("%s" %arr[i]),

output:

Sorted array is:
a m o p w x

answered Oct 30, 2019 at 4:01

Divyesh patel

1,0071 gold badge9 silver badges21 bronze badges

Comments

Paul Panzer · Accepted Answer · 2019-10-30 05:20:46Z

0

Mergesort:

from heapq import merge
from itertools import islice

def _ms(a, n):
    return islice(a,n) if n<2 else merge(_ms(a,n//2),_ms(a,n-n//2))

def mergesort(a):
    return type(a)(_ms(iter(a),len(a)))

# example

import string
import random

L = list(string.ascii_lowercase)
random.shuffle(L)
print(L)
print(mergesort(L))

Sample run:

['h', 'g', 's', 'l', 'a', 'f', 'b', 'z', 'x', 'c', 'r', 'j', 'q', 'p', 'm', 'd', 'k', 'w', 'u', 'v', 'y', 'o', 'i', 'n', 't', 'e']
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

edited Oct 30, 2019 at 5:20

answered Oct 30, 2019 at 4:57

Paul Panzer

53.3k3 gold badges60 silver badges103 bronze badges

Collectives™ on Stack Overflow

How do I alphabetically sort an array of strings without any sort functions? Python

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related