VPF::[Python] Сортировка списка - Форум программистов

Paranorma

Дата 27.1.2007, 19:32 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 102
Регистрация: 1.1.2007

Репутация: 1
Всего: 1

Люди! 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 (ссылка)

(нет голосов)

Загрузка ...

Vadim A. Kazantsev

Профиль
Группа: Участник
Сообщений: 291
Регистрация: 3.12.2006
Где: Moscow, Russia

Репутация: 7
Всего: 14

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'.

Это сообщение отредактировал(а) V.A.KeRneL - 28.1.2007, 21:10

--------------------

«C'est un pense-creux d'ici. C'est le meilleur et le plus irascible homme du monde...» © Ф.М. Достоевский, «Бесы»
---/)/)---(\.../)---(\(\
--(':'=)---(=';'=)---(=':')
(")(")..)-(").--.(")-(..(")(")

doomik

Дата 28.1.2007, 14:24 (ссылка)

(нет голосов)

Загрузка ...

Одинокий волк

Профиль
Группа: Участник
Сообщений: 360
Регистрация: 25.10.2005
Где: #vingrad

Репутация: 3
Всего: 15

Код


# Программа сканирует лист 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

Это сообщение отредактировал(а) doomik - 28.1.2007, 14:26

--------------------

"Единственный способ изучать новый язык программирования - писать на нем
программы."
- Brian Kernighan

Remember, st1ng3r
/server irc.ircline.ru /j #vingrad

Paranorma

Дата 28.1.2007, 15:45 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 102
Регистрация: 1.1.2007

Репутация: 1
Всего: 1

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

doomik

Дата 28.1.2007, 18:02 (ссылка)

(нет голосов)

Загрузка ...

Одинокий волк

Профиль
Группа: Участник
Сообщений: 360
Регистрация: 25.10.2005
Где: #vingrad

Репутация: 3
Всего: 15

Цитата

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

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

Цитата

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

Угу.

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

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

Цитата

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

Пожалуйста smile

--------------------

Paranorma

Дата 28.1.2007, 20:57 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 102
Регистрация: 1.1.2007

Репутация: 1
Всего: 1

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

V.A.KeRneL

Дата 28.1.2007, 21:11 (ссылка)

(нет голосов)

Загрузка ...

Vadim A. Kazantsev

Профиль
Группа: Участник
Сообщений: 291
Регистрация: 3.12.2006
Где: Moscow, Russia

Репутация: 7
Всего: 14

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

Это сообщение отредактировал(а) V.A.KeRneL - 7.2.2007, 11:31

--------------------

doomik

Дата 28.1.2007, 21:19 (ссылка)

(нет голосов)

Загрузка ...

Одинокий волк

Профиль
Группа: Участник
Сообщений: 360
Регистрация: 25.10.2005
Где: #vingrad

Репутация: 3
Всего: 15

Цитата

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

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

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

Код


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

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

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

Это сообщение отредактировал(а) doomik - 28.1.2007, 21:36

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »