Как отсортировать массив строк в алфавитном порядке без каких-либо функций сортировки? питон

Question

При решении следующей задачи: «Предполагая, что у вас есть случайный список строк (например: a, b, c, d, e, f, g), напишите программу, которая будет сортировать строки в алфавитном порядке. Выможет не использовать команду сортировки. "

Я сталкиваюсь с проблемой запуска строк через следующий код, который иногда приводит к дублированию строк в окончательном списке

Я довольно новичок в Python и нашкласс только начал рассматривать numpy и функции в этом модуле, и я не уверен, что они используются в коде (кроме функций сортировки).

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)

Ожидаемый результат ["a", "y "," z "]

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

Фактический результат ...

Введите список строк: ayz

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

Введите список строк: dec

dcdd ['c', 'д ',' д ']

Answer 1

Сортировка выбора: для каждого индекса i списка выберите наименьший элемент в i или после него и поменяйте его на i-ю позицию. Вот реализация в трех строках:

# 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:] - это срез (подмножество) list, начинающийся с i-го элемента.
• min(list)дает вам наименьший элемент в list.
• list.index(element) дает вам (первый) индекс element в list.
• a, b = b, a атомно меняет значения a и b.

Самая хитрая часть этой реализации заключается в том, что когда вы используете index для поиска индекса наименьшего элемента, вам нужно найти индекс в том же самомlist[i:] фрагмент, в котором вы нашли элемент, в противном случае вы можете выбрать дубликат элемента в более ранней части списка. Поскольку вы находите индекс относительно list[i:], вам необходимо добавить к нему i, чтобы получить индекс в пределах всего list.

Answer 2

Вы можете реализовать быструю сортировку для того же:

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]),

вывод:

Sorted array is:
a m o p w x

Answer 3

Слияние:

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))

Пробный прогон:

['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']