Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Центр помощи > [Python] Сортировка списка


Автор: Paranorma 27.1.2007, 19:32
Люди! Help!!!
Задача для меня мега сложная на данном этапе.

Имеется 2 списка: один заполнен числами, второй пустой. Необходимо элементы списка заполненного поместить в список пустой в отсортированном виде по возрастанию. Для этого необходимо использовать метод insert. Это снова на использование  while причем на использование вложенного цикла while. вот во вложенном и должна происходить сортировка с помощью insert в пустой список, я начала, но верно ли это и куда дальше двигаться...

Код

a = [12, 56, 8, 89, 10, 18, 5, 9, 2, 20, 1, 15]
b = []
i = 0
while i < len(a):
    k = a[i]
    while k < len(a):

Автор: V.A.KeRneL 28.1.2007, 12:47
Paranorma, help smile: 
Код

# -*- coding: windows-1251 -*-

a = [12, 56, 8, 89, 10, 18, 5, 9, 2, 20, 1, 15]  # исходный список
b = []  # результирующий список

# [Главный] ИНВАРИАНТ: список `b' упорядочен по неубыванию.
# 
# В качестве дополнительного можно указать: 
# «Либо ``i < len(a)'', лмбо `b' содержит полностью отсортированный списоsк 
# `a'.»

i = 0  # индекс, счётчик для элементов списка `a'
# `while' по всем элементам списка `a'...
while (i < len(a)): 
    #print '>',  # трассировка (вход в главный `while')
    ai = a[i]         # i-ый элемент списка `a'
    j = 0             # индекс, счётчик для элементов списка `b'
    inserted = False  # флаг, указывающий вставили ли мы `ai' в `b', 
                      # или пока нет
    # Пока НЕ прошлись по всему `b' И НЕ вставили в него `ai'...
    while ((j < len(b)) and (not inserted)): 
        #print '.',  # трассировка (вход во вложенный `while')
        bj = b[j]  # j-ый элемент списка `b'
        # Если нашли место в `b', куда можно вставить...
        if (ai < bj): 
            b.insert(j, ai)  # ...вставляем...
            inserted = True  # Вставили `ai' в `b'.
        j += 1  # Переводим к следующему элементу списка `b'.
        #print ', ',  # трассировка (выход из вложенного `while')
    # Если, пройдясь по всему списку `b', мы, всё-таки, не вставили его до 
    # какого либо элемента (в `b' не нашлось элемента меньшего `ai')...
    if (not inserted): 
        b.insert(len(b), ai)  # ...вставляем `ai' в конец списка `b'.
    i += 1  # Переводим к следующему элементу списка `a'.
    #print '<'  # трассировка (выход из главного `while')

print 'a = ', a  # Напечатаем, какой же у нас был исходный список `a'.
print 'b = ', b  # Отобразим результирующий список `b'.


Автор: doomik 28.1.2007, 14:24
Код

# Программа сканирует лист a на наличия самого минимального элемента, если найдено то этот 
# элемент добавляется в новый лист b[] и этот элемент удаляется из старого листа чтоб найти
# второй самый минимальный а потом третий и т.д

a = [12, 56, 8, 89, 10, 18, 5, 9, 2, 20, 1, 15]
b = []
MinTemp = 100 # Максимальное число для нахождения самого маленького числа
Ind = InsInd = j = i =  0
while i < len(a):
    while j < len(a):
        if a[j] < MinTemp: # Если елемент a[j] меньше MinTemp тогда MinTemp получает a[j] а Ind->j 
            MinTemp = a[j]
            Ind = j
        j += 1
    b.insert(InsInd, MinTemp) # Массив b получает Индекс ( InsInd ) и самый маленький элемент MinTemp
    del(a[Ind]) # Удаляем самый маленький элемент из списка a 
    j = 0 
    i = 0 
    MinTemp = 100 # 
    Ind = 0
    InsInd += 1
print b


Лучше чтоб MinTemp получил максимальное число int т.е тогда изменить 
преписать в начале 
Код

import sys


а дальше в место 100 исползовать sys.maxint
Код

MinTemp = sys.maxint


или же сразу без модуля присвоить вот такое вот число:
Код

2147483647



Кстати лучше бы ты старалась сама решать и "ломать голову" от этого эффекта больше ( моё мнение ) smile 

Автор: Paranorma 28.1.2007, 15:45
Я вчера сама долго думала и ничего не заработала, кроме головной боли. На самом деле мне проще из того, что вы мне все тут пишете проанализировать свои ошибки и сделать так, как мне понятнее. Я только насчет MinTemp удивлена, ей присвоено значение 100 # Максимальное число для нахождения самого маленького числа Это ты на основе моего списка написал 100? Но ведь он может быть любым по количеству элементов и тогда уже не определишься какой там максимальный/минимальный элемент. Но все равно большое спасибо.

Автор: doomik 28.1.2007, 18:02
Цитата
Я вчера сама долго думала и ничего не заработала, кроме головной боли

Значит это не довольно долго  smile 

Цитата
Это ты на основе моего списка написал 100?

Угу.

Но я в низу в моём первом посте написал про то что как лучше сделать т.е присвоить MaxTemp максимальное значение int при помощи использования функции sys.maxint из модуля sys.

Программу тестил на разных длиннах листа и с разными элементами - она работает хотя может быть и есть какие-то недоделки которых я не увидел.

Цитата
 
Но все равно большое спасибо. 

Пожалуйста  smile 

Автор: Paranorma 28.1.2007, 20:57
Я функцию sys.maxint еще не изучала, поэтому не могу ее использовать. Не совсем понятно, как она работает. 

Автор: V.A.KeRneL 28.1.2007, 21:11
Paranorma, sys.maxint — это не функция, а константа.

А чем, если не секрет, тебе не понравилось моё решение? 
Оно большое? Так там половина комментариев. Для кого я их писал-то? smile Если их удалить, исходник станет раза в 2 меньше: 
Код

a = [12, 56, 8, 89, 10, 18, 5, 9, 2, 20, 1, 15]
b = []
i = 0
while (i < len(a)): 
    ai = a[i]
    j = 0
    inserted = False
    while ((j < len(b)) and (not inserted)): 
        bj = b[j]
        if (ai < bj): 
            b.insert(j, ai)
            inserted = True
        j += 1
    if (not inserted): 
        b.insert(len(b), ai)
    i += 1
print 'a = ', a
print 'b = ', b


==========================================================================================

Но, в принципе, Paranorma, если тебе больше нравится решение doomik'а, то от него можно открутить инициализацию константой. 
Так получится даже корректнее: 
Код

# Программа сканирует лист a на наличия самого минимального элемента, если найдено то этот 
# элемент добавляется в новый лист b[] и этот элемент удаляется из старого листа чтоб найти
# второй самый минимальный а потом третий и т.д

a = [12, 56, 8, 89, 10, 18, 5, 9, 2, 20, 1, 15]
b = []
if (len(a) > 0):    # <<< 
    MinTemp = a[0]  # <<< Тута модификация...
Ind = InsInd = j = i =  0
while i < len(a): 
    while j < len(a): 
        if a[j] < MinTemp:  # Если елемент a[j] меньше MinTemp тогда MinTemp получает a[j] а Ind->j 
            MinTemp = a[j]
            Ind = j
        j += 1
    b.insert(InsInd, MinTemp)  # Массив b получает Индекс ( InsInd ) и самый маленький элемент MinTemp
    del(a[Ind])  # Удаляем самый маленький элемент из списка a 
    j = 0 
    i = 0 
    if (len(a) > 0):    # <<< 
        MinTemp = a[0]  # <<< ...и тут.
    Ind = 0
    InsInd += 1
print b


Автор: doomik 28.1.2007, 21:19
Цитата
Я функцию sys.maxint еще не изучала, поэтому не могу ее использовать. Не совсем понятно, как она работает. 


Опять же в первом моём посту почти в самом низу я указал большую цифру которую можно использовать в место константы потому что sys.maxint равно 2147483647.

Если использовать цифру хоть больше чем 2147483647 на единицу то переменная преобразуется в тип long что != int 
а проверить можно так

Код

Number = 2147483647
type(Number)
<type 'int'>

Number = 2147483648
type(Number)
<type 'long'>


Насчёт функции ошибся константа это, спасибо V.A.KeRneL починил.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)