написал прогу и вроде все работает только сортировку выводит только 1 цифру с повторением

листинг программы:

Public Class Form1
Dim stroc As String 'дополнительная переменная для обмена
Dim fon As Long, buk As Long 'дополнительные переменные для обмена
Dim A(0 To 10) As Integer
Dim j, i, k, p, Box, t, imax As Integer

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
stroc = TextBox1.Text
TextBox1.Text = TextBox2.Text
TextBox2.Text = stroc
End Sub

Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click
TextBox2.BackColor = Color.DarkMagenta
GroupBox1.BackColor = Color.Gray
End Sub

Private Sub Button3_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button3.Click
TextBox2.BackColor = Color.White
GroupBox1.BackColor = Color.Blue
End Sub

Private Sub Button4_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button4.Click
TextBox3.Text = " "
Randomize()
ReDim A(0 To 10)
For i = 1 To 10
A(i) = Int(101 * Rnd())
TextBox3.Text = TextBox3.Text + " " + Str(A(i)) 'заполнение массива
Next i
End Sub

Private Sub Button5_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button5.Click
For t = 1 To 10
For j = 1 To 9 'организуем 9 просмотров массива
For i = 1 To 9 ' организуем просмотр массива с 1-го по 9-ый элемент
If A(i) > A(i + 1) Then
Call Exchange(i, i + 1) 'вызов процедуры Exchange
End If
' TextBox4.Text = TextBox4.Text + " " + Str(A(i))
Next i
' TextBox4.Text = TextBox4.Text + " " + Str(A(i))
Next j
TextBox4.Text = TextBox4.Text + " " + Str(A(i))
Next t
End Sub

Private Sub Button7_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button7.Click
For t = 1 To 10
For j = 1 To 9 ' организуем 9 просмотров массива
For i = 1 To 9 ' организуем просмотр массива с 1-го по 9-ый элемент
Call max() ' вызов процедуры Max
Next i
Next j
TextBox5.Text = TextBox5.Text + " " + Str(A(j))
Next t
End Sub

Private Sub max()
imax = j
For i = j To 10
If A(i) > A(imax) Then
imax = i
End If
Next i
End Sub

Private Sub Exchange(ByVal k As Integer, ByVal p As Integer)
Box = A(k)
A(k) = A(p)
A(p) = Box
End Sub

Private Sub Button6_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button6.Click
TextBox3.Clear()
TextBox4.Clear()
TextBox5.Clear()
End Sub
End Class

Думаю, вот так оно будет лучше работать - метод пузырьковой сортировки

Нужен алгоритм, который ищет в массиве заданное количество минимальных элементов
и выводит их номера в другой массив. Проблема в том, что
1) Массив не желательно копировать/портить, поэтому алгоритмы сортировки не подходят, да и избыточны они
(мне нужно, скажем, 3 элемента, а сортировщик отсортирует все)
2) Хотелось бы получить результат за один проход.
3) Работать должно как можно быстрее, скорость - главное.

Пока вот что сочинил



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

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

а что нибудь про массив известно, типа какое у него распределение? расход памяти не критичен? могу предложить такой вариант, который подошёл бы для равномерного распределения:
1. найти минимум и максимум
2. поделить длину исходного массива на количество элементов, которые надо извлечь, и помножить это число на некоторый коэффициент, подобранный эмпирически. скажем, 3.
3. поделить интервал на число, полученное в предыдущем пункте, это будет новая верхняя граница. пробежать массив второй раз и запихнуть в выходной массив индексы всех элементов, значения которых меньше этой новой верхней границы
4. отсортировать массив из предыдущего пункта по значению (не по индексу) и взять меньше 3 элемента

с высокой долей вероятности, которая зависит от распределения и коэффициента в п.2 эти 3 элемента окажутся наименьшими в исходном массиве

Гаусово, но с неизвестными характеристиками.

Нужно со 100%. Кроме того, длина массива и требуемое число выводимых номеров минимальных элементов
должно меняться, и эмперически подбирать коэффициенты под каждый случай не хочется.

vo1

А почему сначала просто не найти минимальный элемент за 1 проход. А потом искать элемент, который будет минимальным, но больше или равен тому, который был найден в прошлый раз?

ToSHiC

Ржака , мы не в 80ых , это во первых , а во вторых, чел который думает о таких вещях , здесь не ошивается и не задаёт вопросы про массивы...

Написал на Java за 10 минут. Столько проходов по массиву, сколько элементов надо найти. Ну и не делал проверку на два одинаковых минимальных элемента. Но там не сложно, просто следить за индексами.

Моя нынешняя реализация работает так: копируется массив, затем ищется минимальный элемент с индексом,
затем на этом индексе выставляется большое число (int.MaxValue). Потом опять в этом же массиве
производится поиск минимального элемента и так нужное количество раз.

По поводу больше или равен - если я такое условие поставлю, то все время буду ловить один и тот же
элемент -нужно еще дополнительно указывать проверку, не является ли мой индекс одним из найденных
мной индексов. А это не желательно, т.к. усложняет программу.


Какое количество минимальных элементов? А если больше 3?

Присочинил тут такой алгоритм


Работает пока не совсем корректно, содержит дополнительный цикл, что не есть хорошо.
Идеальный вариант программы должен иметь сложность примерно как то что я в первый раз выложил
и работать как можно быстрее. То, что кое-как выдает нужный результат, уже сделано. Теперь
надо ускорить.


А, понятно. Это плохо...

Просто больше.
Если есть повторяющиеся элементы, то индексы все равно надо(если массив не портить). Хотя есть и другие варианты запоминания элементов, которые уже встречались.




Ступил. Проходов столько, сколько элементов надо найти. Уже поправил пост.



По-моему это не реально без сортировки.

а что, кроме как под x86 уже больше ни подо что не надо писать код?:) ну и количество массивов бывает разное + возможно планируется некоторая оптимизация с целью попадания в кэш процессора и т.д.

мне кажется, алгоритма со сложностью O(n) не получится. я вот только тот придумал, что выше написал

Это смотря какое соотношение количества всех элементов и искомых.

кстати, у квиксорта сложность O(n log n), так что если длина первого массива не очень большая и надо извлечь как минимум несколько значений - то сортировка может даже и быстрее будет работать

Кстати, его можно испортить, запомнить в отдельном массиве то, что мы испортили,
а в конце испорченные элементы обратно восстановить.

Ладно, если нельзя без кучи проходов, значит нельзя. Хоть мой последний алгоритм имеет один проход,
внутренний цикл убивает это преимущество. Есть вариант использовать метод быстрой сортировки,
но он будет давать преимущество для довольно больших значений выбираемых элементов (надо опыты поставить, может это большое число равно двум), да и придется крутить два массива сразу (один исходный, другой - с индексами, изначально заданными по порядку).
Кроме того, нужно проверить, является ли этот алгоритм "тормозом" программы. Ведь количество операций
при увеличении количества элементов для этого алгоритма растет линейно, а для остальной части программы как
2^p, где p - количество минимальных элементов. Скажем, для p = 0..3 этот алгоритм может оказывать существенное
влияние, а для p > 5 вряд ли имеет большое значение. Но, тем не менее, функция должна будет вызываться кучу раз
и должна быть максимально "вылизана" каждая ее часть.

Кстати, длина массива от 8 до 128.


В финале операции, которые делает эта программа, должен будет выполнять микроконтроллер/ПЛИС.
Пока у меня знаний на это не хватает, от меня требуется просто сделать ее на C#.

ToSHiC
Ха, а тебе java что нибудь говорит ? Там пох , для какой ос/платформы пишешь.
И причем здесь архитектура процессора ? Мы опять же, не в 80ых. Не на ассамлёре же пишем ...

?



В итоге j == числу минимальных элементов массива а[].
Бери сколько надо индексов из массива I[].

то есть для микроконтроллеров с несколькими килобайтами памяти на борту тоже на жаве будешь писать и пофиг на память? и для видюх на cuda/opencl, где вполне может быть всего 16 килобайт памяти на мультипроцессор?

zauropod
Алгоритм неверен: что, если минимальный элемент окажется самым первым?
Условие (a[i] <= min) никогда не будет выполнено.

Ладно, спасибо за помощь . Оказалось, этот алгоритм не является слабым местом,
поэтому его оптимизацией займусь в последнюю очередь (наверное, применю быструю сортировку).

Ваше утверждение неверно.
Внимательно посмотрите на первые три строчки.